n<=100000種食物，給每個食物煮熟時間，有q<=500000個操作：在某時刻插入某個食物；查詢熟食中編號最小的并刪除之；查詢是否有編號為id的食物，如果有查詢是否有編號為id的熟食，如果有熟食刪除之，否則輸出其離煮熟的最小時間；查詢編號在[L,R]的熟食有多少。保證操作時間遞增。
可以發現：針對某種食物的信息維護只需要知道其未煮熟的食物中煮熟時間的最小值，而所有的熟食都可以一起維護。為此可以：對每個食物開個隊列存未熟食物，對所有食物開個優先隊列以便及時把熟食從隊列中提出來，并開個以編號為下標的“東西”來維護每個編號的數量和區間信息。
由于只需要單點修改、區間查詢，可以用BIT。至于查熟食中的編號最小可以用BIT上倍增。
這里比較腦殘就寫了線段樹。。然而被卡常卡死了。
1 #include<stdio.h> 2 #include<string.h> 3 #include<algorithm> 4 #include<stdlib.h> 5 #include<queue> 6 //#include<queue> 7 //#include<math.h> 8 //#include<time.h> 9 //#include<iostream> 10 using namespace std; 11 12 int T,n,m; 13 #define maxn 200011 14 #define maxq 500011 15 16 struct SMT 17 { 18 struct Node 19 { 20 int sum; 21 int ls,rs; 22 }a[maxn<<1]; 23 int size; 24 void build(int &x,int L,int R) 25 { 26 x=++size; a[x].sum=0; 27 if (L==R) {a[x].ls=a[x].rs=0; return;} 28 const int mid=(L+R)>>1; 29 build(a[x].ls,L,mid); build(a[x].rs,mid+1,R); 30 } 31 void build() {size=0; int x; build(x,1,n);} 32 void up(int x) {a[x].sum=a[a[x].ls].sum+a[a[x].rs].sum;} 33 int ql,qr,v; 34 bool Add(int x,int L,int R) 35 { 36 if (L==R) 37 { 38 if (v==-1 && a[x].sum==0) return 0; 39 a[x].sum+=v; return 1; 40 } 41 else 42 { 43 const int mid=(L+R)>>1;bool ans; 44 if (ql<=mid) ans=Add(a[x].ls,L,mid); 45 else ans=Add(a[x].rs,mid+1,R); 46 up(x); return ans; 47 } 48 } 49 bool add(int x,int v) {ql=x; this->v=v; return Add(1,1,n);} 50 int Find(int x,int L,int R) 51 { 52 if (L==R) return L; 53 const int mid=(L+R)>>1; 54 if (a[a[x].ls].sum>0) return Find(a[x].ls,L,mid); 55 return Find(a[x].rs,mid+1,R); 56 } 57 int find() {return Find(1,1,n);} 58 int Query(int x,int L,int R) 59 { 60 if (ql<=L && R<=qr) return a[x].sum; 61 int mid=(L+R)>>1,ans=0; 62 if (ql<=mid) ans+=Query(a[x].ls,L,mid); 63 if (qr> mid) ans+=Query(a[x].rs,mid+1,R); 64 return ans; 65 } 66 int query(int L,int R) {ql=L; qr=R; return Query(1,1,n);} 67 }smt; 68 69 struct qnode 70 { 71 int v,id; 72 bool operator > (const qnode &b) const {return v>b.v;} 73 }; 74 priority_queue<qnode,vector<qnode>,greater<qnode> > qtot; 75 queue<int> q[maxn]; 76 77 int a[maxn]; 78 int qread() 79 { 80 char c;int s=0; while (!((c=getchar())>='0' && c<='9')); 81 do s=s*10+c-'0'; while ((c=getchar())>='0' && c<='9'); return s; 82 } 83 void write(int x) 84 { 85 if (!x) {putchar('0');putchar('\n');return;} 86 char buf[15]; int lb=0; 87 while (x) {buf[++lb]=x%10; x/=10;} 88 for (;lb;lb--) putchar(buf[lb]+'0'); putchar('\n'); 89 } 90 int main() 91 { 92 scanf("%d",&T); 93 while (T--) 94 { 95 scanf("%d",&n); 96 for (int i=1;i<=n;i++) a[i]=qread(); 97 for (int i=1;i<=n;i++) while (!q[i].empty()) q[i].pop(); 98 while (!qtot.empty()) qtot.pop(); 99 smt.build(); 100 scanf("%d",&m); 101 int t,op,id,x,y; 102 while (m--) 103 { 104 t=qread(),op=qread(); 105 while (!qtot.empty() && qtot.top().v<=t) smt.add(qtot.top().id,1),q[qtot.top().id].pop(),qtot.pop(); 106 if (op==0) 107 { 108 id=qread(); 109 q[id].push(t); 110 qtot.push((qnode){t+a[id],id}); 111 } 112 else if (op==1) 113 { 114 if (smt.a[1].sum==0) puts("Yazid is angry."); 115 else 116 { 117 int ans=smt.find(); 118 write(ans); 119 smt.add(ans,-1); 120 } 121 } 122 else if (op==2) 123 { 124 id=qread(); 125 if (smt.add(id,-1)) puts("Succeeded!"); 126 else if (q[id].empty()) puts("YJQQQAQ is angry."); 127 else write(q[id].front()+a[id]-t); 128 } 129 else 130 { 131 x=qread(),y=qread(); 132 write(smt.query(x,y)); 133 } 134 } 135 } 136 return 0; 137 }
?
 方法)
