cdq分治解决区间问题

如题，已知一个数列，你需要进行下面两种操作：

1.将某一个数加上x

2.求出某区间每一个数的和

输入输出格式

输入格式：

第一行包含两个整数N、M，分别表示该数列数字的个数和操作的总个数。

第二行包含N个用空格分隔的整数，其中第i个数字表示数列第i项的初始值。

接下来M行每行包含3个整数，表示一个操作，具体如下：

操作1：格式：1 x k 含义：将第x个数加上k

操作2：格式：2 x y 含义：输出区间[x,y]内每个数的和

输出格式：

输出包含若干行整数，即为所有操作2的结果。

输入输出样例

输入样例#1：复制

输出样例#1：复制

14

16

说明

时空限制：1000ms,128M

数据规模：

对于30%的数据：N<=8，M<=10

对于70%的数据：N<=10000，M<=10000

对于100%的数据：N<=500000，M<=500000

样例说明：

故输出结果14、16

然而这个代码T了QAQ

#include<cstdio>

#include<algorithm>

const int maxn = ;

inline int read() {

    int x=,f=;char c=getchar();

    while(c<''||c>'') {

        if(c=='-')f=-;c=getchar();

    }

    while(c<=''&&c>='') {

        x=x*+c-'',c=getchar();

    }

    return x*f;

}

int n,m,tot,t,ans[maxn];

struct node{

    int x,key,id,kind,bl;

    bool operator < (const node&a)const {

        if(x!=a.x) return x<a.x;

        else return kind<a.kind;

    }

}q[maxn],tmp[maxn];

void cdq(int l,int r) {

    if(l==r) return;

    int sum=;

    int mid=l+r>>,ll=l,rr=mid+;

    for(int i=l;i<=r;i++) {

        if(q[i].kind==&&q[i].id<=mid) sum+=q[i].key;

        else if(q[i].kind==&&q[i].id>mid)  ans[q[i].bl]+=q[i].key*sum;

    }

    for(int i=l;i<=r;i++) {

        if(q[i].id<=mid)tmp[ll++]=q[i];

        else tmp[rr++]=q[i];

    }

    for(int i=l;i<=r;i++) q[i]=tmp[i];

    cdq(l,mid);cdq(mid+,r);

}

int main()

{

    n=read(),m=read();

    for(int x,i=;i<=n;i++) {

        x=read();

        q[++tot].x=i;q[tot].key=x;q[tot].id=tot;q[tot].kind=;

    }

    for(int x,y,z;m;m--) {

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

        if(x&) {

            q[++tot].x=y;q[tot].key=z;q[tot].id=tot;q[tot].kind=;

        }

        else {

            q[++tot].x=y-;q[tot].key=-;q[tot].id=tot;q[tot].kind=;q[tot].bl=++t;

            q[++tot].x=z;q[tot].key=;q[tot].id=tot;q[tot].kind=;q[tot].bl=t;//id : kth operator ,x:the location of the op ;bl : the group of the query sum

        }

    }

    std::sort(q+,q+tot+);

    cdq(,tot);

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

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

    return ;

}

巴特西

cdq分治解决区间问题

输入输出格式

输入输出样例

说明

最新文章

热门文章