BZOJ-2683/1176: 简单题

[文章目录]

Descripton

你有一个N*N的棋盘,每个格子内有一个整数,初始时的时候全部为0,现在需要维护两种操作:
1 x y A,1<=x,y<=N,A是正整数,将格子x,y里的数字加上A
2 x1 y1 x2 y2,1<=x1<= x2<=N,1<=y1<= y2<=N:输出x1 y1 x2 y2这个矩形内的数字和
3 终止程序

话说以前怎么能够傻到以为这道题就是个splay。。。

将询问按时间分治,考虑前期修改对后期询问的影响,将询问子矩阵容斥,变成四个询问。然后就变成了三维偏序统计权值和的问题了,处理影响的时候用树状数组维护和。
话说每到一个区间进行sort的常数真是感人。懒得改归并了。

以下是2683(慢到死)的代码:

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int n,tot,f[501000];
struct node
{
    int id,x,y,A,ans;
}a[801000];
bool cmp1(node x,node y){return x.x==y.x?x.id<y.id:x.x<y.x;}
bool cmp2(node x,node y){return x.id<y.id;}
void fix(int x,int y) {while(x<=n) f[x]+=y,x+=-x&x;}
void clear(int x) {while(x<=n) f[x]=0,x+=-x&x;}
int query(int x)
{
    if(!x) return 0; int re=0; 
    while(x>0) re+=f[x],x-=-x&x;
    return re;
}
void solve(int l,int r)
{
    if(l==r) return ;
    int mid=l+r>>1;
    solve(l,mid); sort(a+l,a+r+1,cmp1);
    for(int i=l;i<=r;++i)
    {
        if(a[i].id<=mid&&a[i].A) fix(a[i].y,a[i].A);
        if(a[i].id>mid&&!a[i].A) a[i].ans+=query(a[i].y);
    }
    sort(a+l,a+r+1,cmp2);
    for(int i=l;i<=r;++i)
        if(a[i].A) clear(a[i].y);
    solve(mid+1,r);
}
int main()
{
    scanf("%d",&n); int sw,x,xx,y,yy;
    while(1) 
    {
        scanf("%d",&sw);
        if(sw==3) break;
        if(sw==1)
        {
            tot++;
            scanf("%d%d%d",&a[tot].x,&a[tot].y,&a[tot].A);
            a[tot].id=tot;
        }
        else
        {
            scanf("%d%d%d%d",&x,&y,&xx,&yy);
            tot++; a[tot].id=tot; a[tot].x=x-1; a[tot].y=y-1;
            tot++; a[tot].id=tot; a[tot].x=xx;  a[tot].y=y-1;
            tot++; a[tot].id=tot; a[tot].x=x-1; a[tot].y=yy;
            tot++; a[tot].id=tot; a[tot].x=xx;  a[tot].y=yy;
        }
    }
    solve(1,tot); int i=1;
    while(i<=tot)
    {
        if(a[i].A) ++i;
        else printf("%d\n",a[i+3].ans-a[i+2].ans-a[i+1].ans+a[i].ans),i+=4;
    }
    return 0;
}

发表评论

邮箱地址不会被公开。 必填项已用*标注