P3527 [POI2011]MET-Meteors

　　整体二分！
代码
 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 typedef long long LL;
 4 
 5 inline int read() {
 6     int x=0,f=1;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-1;
 7     for (;isdigit(ch);ch=getchar())x=x*10+ch-'0';return x*f;
 8 }
 9 
10 const int N = 300010;
11 int Ans[N],A[N],B1[N],B2[N],T[N];
12 vector <int> v[N];
13 struct OPT{
14     int l,r,val;
15 }OP[N];
16 
17 struct BIT{
18     int n;
19     LL sum[N];
20     inline void update(int l,int r,int v) {
21         for (int p=l; p<=n; p+=p&(-p)) sum[p] += v;
22         for (int p=r+1; p<=n; p+=p&(-p)) sum[p] -= v;
23         if (l > r) for (int p=1; p<=n; p+=p&(-p)) sum[p] += v;
24     }
25     inline LL query(int p) { // LL
26         LL ans = 0;
27         for (; p; p-=p&(-p)) ans += sum[p];
28         return ans;
29     }
30     inline void clear(int l,int r) {
31         for (int p=l; p<=n&&sum[p]; p+=p&(-p)) sum[p] = 0;
32         for (int p=r+1; p<=n&&sum[p]; p+=p&(-p)) sum[p] = 0;
33         if (l > r) for (int p=1; p<=n&&sum[p]; p+=p&(-p)) sum[p] = 0;
34     }
35 }bit;
36 
37 void solve(int Head,int Tail,int L,int R) { // 询问的队列（即国家）[Head,Tail]，答案[L,R]次之间 
38     if (Head > Tail) return; 
39     if (L == R) {
40         for (int i=Head; i<=Tail; ++i) Ans[A[i]] = L;
41         return; 
42     }
43     int M = (L + R) / 2,p1 = 0,p2 = 0;
44     for (int i=L; i<=M; ++i) 
45         bit.update(OP[i].l,OP[i].r,OP[i].val);
46     for (int i=Head; i<=Tail; ++i) {
47         int now = A[i]; // 国家 
48         LL sum = 0;
49         for (int j=0,lim=v[now].size(); j<lim; ++j) 
50             if ((sum += bit.query(v[now][j])) >= T[now]) break;;
51         if (sum >= T[now]) B1[++p1] = A[i];
52         else T[now] -= sum,B2[++p2] = A[i];
53     }
54     for (int i=L; i<=M; ++i) bit.clear(OP[i].l,OP[i].r);
55     for (int i=1; i<=p1; ++i) A[Head+i-1] = B1[i];
56     for (int i=1; i<=p2; ++i) A[Head+p1+i-1] = B2[i];
57     solve(Head,Head+p1-1,L,M);
58     solve(Head+p1,Tail,M+1,R);
59 }
60 
61 int main() {
62     int n,m,k;
63     n = read();
64     bit.n = m = read();
65     for (int i=1; i<=m; ++i) v[read()].push_back(i); // 第read()个国家的空间站i
66     for (int i=1; i<=n; ++i) T[i] = read(),A[i] = i;
67     k = read();
68     for (int i=1; i<=k; ++i) 
69         OP[i].l = read(),OP[i].r = read(),OP[i].val = read();
70     OP[++k] = (OPT){m+1,m+1,0}; // 特判不行的情况 
71     
72     solve(1,n,1,k);
73     for (int i=1; i<=n; ++i) printf(Ans[i]==k?"NIE
":"%d
",Ans[i]);
74     return 0;
75 }