BZOJ1176---[Balkan2007]Mokia （CDQ分治 + 树状数组）

题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=1176

CDQ第一题，warush了好久。。

CDQ分治推荐论文：

1 《从＜Cash＞谈一类分治算法的应用》陈丹琦

2 《浅谈数据结构题的几个非经典解法》许昊然

关于CDQ分治，两种要求：①操作不相互影响 ②可以离线处理

题目描述是有问题的，，初始时全部为0，不是s

题意：二维平面内，两种操作，1 x y v ，位于（x,y）的值加上v.。。2 x1,y1,x2,y2，，（x1,y1） (x2,y2)分别矩形的左上角右下角，查询矩形内所有元素的和。

大致思路，在x这一维上进行分治，然后y这一维直接就可以用树状数组乱搞了。

 #include <cstdio>

 #include <cstdlib>

 #include <cstring>

 #include <algorithm>

 using namespace std;

 const int maxb = 2e6+;

 struct Node

 {

     int x,y,delt;

     int flag,idx;

     Node(){}

     Node(int _x,int _y,int _delt,int _flag,int _idx):

         x(_x),y(_y),delt(_delt),flag(_flag),idx(_idx){};

     bool operator < (const Node &rhs)const

     {

         return x < rhs.x || (x == rhs.x && y < rhs.y);

     }

 }a[];

 struct BIT

 {

     int c[maxb],MAX;

     inline int lowbit(int x)

     {

         return x & -x;

     }

     void add(int x,int val)

     {

         while (x <= MAX)

         {

             c[x] += val;

             x += lowbit(x);

         }

     }

     int sum(int x)

     {

         int res = ;

         while (x > )

         {

             res += c[x];

             x -= lowbit(x);

         }

         return res;

     }

 }arr;

 //---------------------------------------------

 int ans[];

 void CDQ(int l,int r)

 {

     if (l  == r)

         return;

     int mid = (l + r) >> ;

     CDQ(l,mid);

     CDQ(mid+,r);

     int j = l;

     for (int i = mid + ; i <= r; i++)

     {

         if (a[i].flag == )

         {

             for ( ; j <= mid && a[j].x <= a[i].x; j++)

             {

                 if (a[j].flag == )

                 {

                     arr.add(a[j].y,a[j].delt);

                 }

             }

             ans[a[i].idx] += arr.sum(a[i].y) * a[i].delt;

         }

     }

     for (int i = l; i < j; i++)

         if (a[i].flag == )

             arr.add (a[i].y,-a[i].delt);

     inplace_merge (a+l,a+mid+,a+r+);                   // 合并区间 [l,mid+1) [mid+1,r+1)

 }

 int main(void)

 {

     #ifndef ONLINE_JUDGE

         freopen("in.txt","r",stdin);

     #endif // ONLINE_JUDGE

     int s,w;

     while (~scanf ("%d%d",&s,&w))

     {

         int op;

         int tot = ,totq = ;

         arr.MAX = w;

         memset(ans,,sizeof(ans));

         while (scanf ("%d",&op), op != )

         {

             if (op == )

             {

                 int x,y,delt;

                 scanf ("%d%d%d",&x,&y,&delt);

                 a[tot] = Node(x,y,delt,,tot);

                 tot++;

             }

             if (op == )

             {

                 int x1,y1,x2,y2;

                 scanf ("%d%d%d%d",&x1,&y1,&x2,&y2);

                 a[tot] = Node(x1-, y1-,  , , totq); tot++;

                 a[tot] = Node(x2,   y1-, -, , totq); tot++;

                 a[tot] = Node(x1-, y2,   -, , totq); tot++;

                 a[tot] = Node(x2,   y2,    , , totq); tot++;

                 totq++;

             }

         }

         CDQ (,tot-);

         for (int i = ; i < totq; i++)

             printf("%d\n",ans[i]);

     }

     return ;

 }

巴特西

BZOJ1176---[Balkan2007]Mokia （CDQ分治 + 树状数组）

最新文章

热门文章