[BZOJ2989]数列 CDQ分治


原题链接
查询曼哈顿距离内的点个数,转成切比雪夫距离就变成了查询矩形内点的个数,而修改操作实际上是插入新点操作,因此用CDQ分治或kdtree都可以轻松解决.

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define N 502333
using namespace std;
const int maxa=160000;
int n,m;
int ans[N],tim;
struct Node
{
    int x,y,opt,id;
}a[N],tmp[N];
int arr[N];
inline bool operator<(const Node a,const Node b)
{
    return a.x<b.x||((a.x==b.x&&a.y<b.y)||(a.x==b.x&&a.y==b.y&&a.id<b.id));
}
inline void modify(int x,int y)//其实是插入一个点(x,y)
{
    arr[x]=y;
    x=x-y,y=2*y+x;
    a[++tim].x=x,a[tim].y=y;
}
int qcnt;
inline void query(int i,int k)
{
    qcnt++;
    int x=i-arr[i],y=i+arr[i];
    a[++tim].x=x+k,a[tim].y=min(y+k,maxa),a[tim].opt=1,a[tim].id=qcnt;
    a[++tim].x=x+k,a[tim].y=max(y-k-1,0),a[tim].opt=-1,a[tim].id=qcnt;
    a[++tim].x=x-k-1,a[tim].y=min(y+k,maxa),a[tim].opt=-1,a[tim].id=qcnt;
    a[++tim].x=x-k-1,a[tim].y=max(y-k-1,0),a[tim].opt=1,a[tim].id=qcnt;
}
int sum[maxa+2333];
inline void fix(int x,int val)
{
    for(;x<=maxa;x+=x&(-x))sum[x]+=val;
}
inline int getsum(int x)
{
    int re=0;
    for(;x;x-=x&(-x))re+=sum[x];
    return re;
}
void cdq(int l,int r)
{
    if(l==r)return;
    int mid=(l+r)>>1;
    cdq(l,mid),cdq(mid+1,r);
    int lp=l,rp=mid+1,i;
    for(;rp<=r;++rp)
    {
        while(lp<=mid&&a[lp]<a[rp])
        {
            if(!a[lp].id)fix(a[lp].y,1);
            ++lp;
        }
        if(a[rp].id)ans[a[rp].id]+=a[rp].opt*getsum(a[rp].y);
    }
    for(i=l;i<lp;++i)if(!a[i].id)fix(a[i].y,-1);
    lp=l,rp=mid+1;
    for(i=l;i<=r;++i)
    {
        if(lp>mid)tmp[i]=a[rp++];
        else if(rp>r)tmp[i]=a[lp++];
        else if(a[lp]<a[rp])tmp[i]=a[lp++];
        else tmp[i]=a[rp++];
    }
    for(i=l;i<=r;++i)a[i]=tmp[i];
}
int main()
{
    char s[10];
    int i,x,y;
    cin>>n>>m;
    for(i=1;i<=n;++i)
    {
        scanf("%d",&arr[i]);
        modify(i,arr[i]);
    }
    for(i=1;i<=m;++i)
    {
        scanf("%s%d%d",s,&x,&y);
        if(s[0]=='M')modify(x,y);
        else query(x,y);
    }
    cdq(1,tim);
    for(i=1;i<=qcnt;++i)printf("%d\n",ans[i]);
    return 0;
}
/*
4 3
2 4 3 4
Query 3 1
Query 3 2
Query 3 3
*/

发表评论

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