BZOJ 2989: 数列 & 4170: 极光

给定一个长度为 n 的正整数数列 a[i]。
定义 2 个位置的 graze 值为两者位置差与数值差的和，即 graze(x,y)=|x-y|+|a[x]-a[y]|。
2 种操作（k 都是正整数）：
1.Modify x k：将第 x 个数的值修改为 k。
2.Query x k：询问有几个 i 满足 graze(x,i)<=k。因为可持久化数据结构的流行，询问不仅要考虑当前数列，还要考虑任意历史版本，即统计任意位置上出现过的任意数值与当前的 a[x]的 graze 值<=k 的对数。（某位置多次修改为同样的数值，按多次统计）

Input

第 1 行两个整数 n,q。分别表示数列长度和操作数。
第 2 行 n 个正整数，代表初始数列。
第 3--q+2 行每行一个操作。

Output

对于每次询问操作，输出一个非负整数表示答案

Sample Input

3 5
2 4 3
Query 2 2
Modify 1 3
Query 2 2
Modify 1 2
Query 1 1

Sample Output

2
3
3

HINT

N<=60000 修改操作数<=40000 询问<=60000 Max{a[i]}含修改<=100000

Solution

这道题其实是维护两种操作，向平面上加点，查询菱形内点数。
把 $(x,y)$ 变为 $(x+y,x-y)$，菱形就变成了正方形。
假设某个询问是以 $(x0,y0)$ 为中心，边长为 $2k$ 的正方形，那么可以拆成两个，一个是 $x\ge x0-k$ 且 $x\le x0+k$ 且 $y\le y0+k$ 的点数，另一个是 $x\ge x0-k$ 且 $x\le x0+k$ 且 $y< y0-k$ 的点数，把两个询问做差原询问相同。
那么可以 CDQ 分治，按 $y$ 排序，$x$ 用树状数组维护。

Code

#include<bits/stdc++.h>

using namespace std;

int n,m,s[60001],ans[60000],ac,qc,mx;

struct query
{
    int x,y,k,id;char op;
}q[230000],tmp[230000];

inline void add(int x,int y){q[qc].x=x+y,q[qc].y=x-y,qc++,mx=max(mx,x+y);}

int p[160001];
inline void pl(int x){for(;x<=mx;x+=x&-x)p[x]++;}
inline int qr(int x){if(x<=0)return 0;int r=0;for(x=min(x,mx);x;x^=x&-x)r+=p[x];return r;}
inline void cl(int x){for(;x<=mx;x+=x&-x)p[x]=0;}

void work(int l,int r)
{
    if(l==r)return;
    int mid=(l+r)>>1;
    work(l,mid),work(mid+1,r);
    int i1=l,i2=mid+1,ti=l;
    for(;i2<=r;tmp[ti++]=q[i2++])
    {
        for(;i1<=mid&&q[i1].y<=q[i2].y;tmp[ti++]=q[i1++])
            if(!q[i1].op)pl(q[i1].x);
        if(q[i2].op)
        {
            if(q[i2].op==1)
                ans[q[i2].id]+=qr(q[i2].x+q[i2].k)-qr(q[i2].x-q[i2].k-1);
            else
                ans[q[i2].id]+=qr(q[i2].x-q[i2].k-1)-qr(q[i2].x+q[i2].k);
        }
    }
    for(;i1<=mid;tmp[ti++]=q[i1++]);
    for(i1=l;i1<=mid;i1++)if(!q[i1].op)cl(q[i1].x);
    for(i1=l;i1<=r;i1++)q[i1]=tmp[i1];
}

int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        scanf("%d",s+i),add(i,s[i]);
    char tmp[10];int a,b;
    while(m--)
    {
        scanf("%s%d%d",tmp,&a,&b);
        if(tmp[0]=='M')
            add(a,s[a]=b);
        else
        {
            int x=a+s[a],y=a-s[a];
            q[qc].x=x,q[qc].y=y+b,q[qc].k=b,q[qc].id=ac,q[qc].op=1,qc++;
            q[qc].x=x,q[qc].y=y-b-1,q[qc].k=b,q[qc].id=ac,q[qc].op=2,qc++;
            ac++;
        }
    }
    work(0,qc-1);
    for(int i=0;i<ac;i++)
        printf("%d\n",ans[i]);
}

日期： 2017-01-08

标签： BZOJ CDQ分治 树状数组

这是一篇旧文，原始文章及评论可在 https://oldblog.mcfx.us/archives/163/ 查看。