cdq分治总结（题目合集）

灰太狼 2024-04-17 21:57 67阅读 0赞

## 1、The Preliminary Contest for ICPC Asia Nanjing 2019 A. The beautiful values of the palace ##

## 题意：给出一个n\*n（n为奇数）的蛇形矩阵，将其中的m个点的值改为各位数之后，给出p组询问，查询子矩阵的和（必须是m个点集中的点，其他的点可看成值为0）。 ##

## 分析：数组求和或者矩阵求和，一般树状数组和线段树就可以做，这里用cdq分治写的。和子矩阵修改，子矩阵求和那题几乎是一样的。cdq分治总结可以参考[https://www.cnblogs.com/Parsnip/p/10816330.html][https_www.cnblogs.com_Parsnip_p_10816330.html]。 ##

## 代码： ##

#include <bits/stdc++.h>
    using namespace std;
    #define ll long long
    const int N=1e6+5,M=800020;
    int n,m,cnt,tot,ans[M];
    struct BIT
    {
        int p[N];
        inline int lowbit(int x){return x&(-x);}
        inline void insert(int pos,int val)
        {
            for (;pos<=n;pos+=lowbit(pos))
                p[pos] += val;
        }
        inline int query(int pos)
        {
            int res = 0;
            for (;pos;pos-=lowbit(pos))
                res += p[pos];
            return res;
        }
        inline void cl() {
            memset(p,0,sizeof(p));
        }
    }tree;
    struct order
    {
        int flag,x,y,val;
        bool operator < (order p)
        {
            if ( x ^ p.x ) return x < p.x;
            if ( y ^ p.y ) return y < p.y;
            return flag < p.flag;
        }
    }a[M],cur[M];
    
    int get(int x,int y)
    {
        ll ans = 0,sum = 0;
        ll t = max(abs(x-(n+1)/2),abs(y-(n+1)/2));
        sum = 1LL*n*n - (2*t+1)*(2*t+1);
        if(x>=y) sum += abs((n+1)/2+t-x)+abs((n+1)/2+t-y)+1;
        else sum += 2*(2*t+1)-1+abs((n+1)/2-t-x)+abs((n+1)/2-t-y);
        while(sum)
            ans+=sum%10,sum/=10;
        return ans;
    }
    
    
    inline void cdq(int l,int r)
    {
        if ( l == r ) return;
        int mid = l+r >> 1 , p = l , q = mid+1 , t = l-1;
        cdq(l,mid); cdq(mid+1,r);
        while ( p <= mid && q <= r )
        {
            if ( a[p] < a[q] )
            {
                if ( a[p].flag == 1 ) tree.insert(a[p].y,a[p].val);
                cur[++t] = a[p++];
            }
            else
            {
                if ( a[q].flag == 2 ) ans[ a[q].val ] += tree.query(a[q].y);
                if ( a[q].flag == 3 ) ans[ a[q].val ] -= tree.query(a[q].y);
                cur[++t] = a[q++];
            }
        }
        while ( q <= r )
        {
            if ( a[q].flag == 2 ) ans[ a[q].val ] += tree.query(a[q].y);
            if ( a[q].flag == 3 ) ans[ a[q].val ] -= tree.query(a[q].y);
            cur[++t] = a[q++];
        }
        for (int i=l;i<p;i++)
            if ( a[i].flag == 1 )
                tree.insert(a[i].y,-a[i].val);
        while ( p <= mid ) cur[++t] = a[p++];
        for (int i=l;i<=r;i++) a[i] = cur[i];
    }
    
    int T,p;
    inline void input() {
        scanf("%d",&T);
        while(T--) {
            cnt = 0;
            tot = 0;
            tree.cl();
            memset(ans,0,sizeof(ans));
            scanf("%d%d%d",&n,&m,&p);
            for(int i=1;i<=m;i++) {
                int x,y;
                scanf("%d%d",&x,&y);
                int val = get(x,y);
                a[++cnt] = (order){1,x,y,val};
            }
            for(int i=1;i<=p;i++) {
                int x1,y1,x2,y2;
                scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
                a[++cnt] = (order){2,x2,y2,++tot};
                a[++cnt] = (order){2,x1-1,y1-1,tot};
                a[++cnt] = (order){3,x1-1,y2,tot};
                a[++cnt] = (order){3,x2,y1-1,tot};
            }
            cdq(1,cnt);
            for (int i=1;i<=tot;i++)
                printf("%d\n",ans[i]);
        }
    }
    
    int main(void) {
        input();
        return 0;
    }

[https_www.cnblogs.com_Parsnip_p_10816330.html]: https://www.cnblogs.com/Parsnip/p/10816330.html