1176: [Balkan2007]Mokia

链接

分析

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

代码

 #include<bits/stdc++.h>

 using namespace std;

 typedef long long LL;

 inline int read() {

     int x=,f=;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-;

     for (;isdigit(ch);ch=getchar())x=x*+ch-'';return x*f;

 }

 int ans[],W;

 struct Que{

     int ty,x,y,w,id;

     bool operator < (const Que &a) const {

         return x == a.x ? ty < a.ty : x < a.x;

     }

 }A[*++],B[*++];

 struct Bit{

     int sum[];

     void update(int p,int v) {

         for (; p<=W; p+=p&(-p)) sum[p] += v;

     }

     int query(int p) {

         int ans = ;

         for (; p; p-=p&(-p)) ans += sum[p];

         return ans;

     }

     void clear(int p) {

         for (; p<=W&&sum[p]; p+=p&(-p)) sum[p] = ;

     }

 }bit;

 void CDQ(int L,int R) {

     if (L == R) return ;

     int M = (L + R) >> ;

     CDQ(L,M);

     CDQ(M+,R);

     int i = L, j = M + ,k = L;

     while (i <= M && j <= R) {

         if (A[i] < A[j]) {

             if (A[i].ty == ) bit.update(A[i].y,A[i].w);

             B[k++] = A[i++];

         }

         else {

             if (A[j].ty == ) ans[A[j].id] += A[j].w * bit.query(A[j].y);

             B[k++] = A[j++];

         }

     }

     while (i <= M) B[k++] = A[i++];

     while (j <= R) {

         ans[A[j].id] += A[j].w * bit.query(A[j].y);

         B[k++] = A[j++];

     }

     for (int i=L; i<=R; ++i) {

         bit.clear(A[i].y);

         A[i] = B[i];

     }

 }

 int main() {

     W = read();W = read(); // 把W在这里int了一下，然后。。。

     int Index = ,QueIndex = ;

     while () {

         int opt = read();

         if (opt==) break;

         if (opt==) {

             int a = read(),b = read(),val = read();

             A[++Index] = (Que){,a,b,val,};

         }

         else {

             int a1 = read(),b1 = read(),a2 = read(),b2 = read();

             A[++Index] = (Que){,a1-,b1-,,++QueIndex};

             A[++Index] = (Que){,a1-,b2,-,QueIndex};

             A[++Index] = (Que){,a2,b1-,-,QueIndex};

             A[++Index] = (Que){,a2,b2,,QueIndex};

         }

     }

     CDQ(,Index);

     for (int i=; i<=QueIndex; ++i) printf("%d\n",ans[i]);

     return ;

 }