1176: [Balkan2007]Mokia

1176: [Balkan2007]Mokia

1176: [Balkan2007]Mokia

 链接

分析

　　三维偏序问题，CDQ分治论文题。

代码

 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 int ans[10010],W;
11 struct Que{
12     int ty,x,y,w,id;
13     bool operator < (const Que &a) const {
14         return x == a.x ? ty < a.ty : x < a.x;
15     }
16 }A[160000*4+10000+10],B[160000*4+10000+10];
17 
18 struct Bit{
19     int sum[2000010];
20     void update(int p,int v) {
21         for (; p<=W; p+=p&(-p)) sum[p] += v;
22     }
23     int query(int p) {
24         int ans = 0;
25         for (; p; p-=p&(-p)) ans += sum[p];
26         return ans;
27     }
28     void clear(int p) {
29         for (; p<=W&&sum[p]; p+=p&(-p)) sum[p] = 0;
30     }
31 }bit;
32 
33 void CDQ(int L,int R) {
34     if (L == R) return ;
35     int M = (L + R) >> 1;
36     CDQ(L,M);
37     CDQ(M+1,R);
38     int i = L, j = M + 1,k = L;
39     while (i <= M && j <= R) {
40         if (A[i] < A[j]) {
41             if (A[i].ty == 0) bit.update(A[i].y,A[i].w);
42             B[k++] = A[i++];
43         }
44         else {
45             if (A[j].ty == 1) ans[A[j].id] += A[j].w * bit.query(A[j].y);
46             B[k++] = A[j++];
47         }
48     }
49     while (i <= M) B[k++] = A[i++];
50     while (j <= R) {
51         ans[A[j].id] += A[j].w * bit.query(A[j].y);
52         B[k++] = A[j++];
53     }
54     for (int i=L; i<=R; ++i) {
55         bit.clear(A[i].y);
56         A[i] = B[i];
57     }
58 }
59 int main() {
60     
61     W = read();W = read(); // 把W在这里int了一下，然后。。。 
62     int Index = 0,QueIndex = 0;
63     
64     while (1) {    
65         int opt = read();
66         if (opt==3) break;
67         if (opt==1) {
68             int a = read(),b = read(),val = read();
69             A[++Index] = (Que){0,a,b,val,0};
70         }
71         else {
72             int a1 = read(),b1 = read(),a2 = read(),b2 = read();
73             A[++Index] = (Que){1,a1-1,b1-1,1,++QueIndex};
74             A[++Index] = (Que){1,a1-1,b2,-1,QueIndex};
75             A[++Index] = (Que){1,a2,b1-1,-1,QueIndex};
76             A[++Index] = (Que){1,a2,b2,1,QueIndex};
77         }
78     }
79     CDQ(1,Index);
80     for (int i=1; i<=QueIndex; ++i) printf("%dn",ans[i]);
81     return 0;
82 }

转载于:.html