首页 > 代码库 > poj-3468

poj-3468

2024-07-15 08:10:07   219人阅读

等到我大脑已经残了，耳朵也鸣了，它终于过了。时间都哪去了，一天半就没了。

这个题目有2个操作：修改一个区间的值（注意，它是把这个区间所有单位在原始值加上一个V值，并不是简单的直接改成V，所以在修改的时候，应该是累加，如：to[cur]+=V，而不是to[cur] = v）,另外一个操作就是查询，这个题目主要运用了线段树，懒惰标记，因为它的查询是对一个区间进行的，若是对一个元结点进行查询，可以只用简单的线段树操作就OK了。看代码，此代码纠错机制由LH and TK大神倾力打造。

#include<iostream>#include<cstring>#include<queue>#include<algorithm>#define maxn 300010#define LL long longusing namespace std;int num[100010];LL to[maxn];LL ans;int read;struct H{    int l,r;    long long sum;} trees[maxn];void pushdown(int jd){    int mid = (trees[jd].l + trees[jd].r)/2;    if(to[jd] != 0)    {        to[2*jd] += to[jd];        to[2*jd+1] += to[jd];        trees[2*jd].sum += (mid - trees[jd].l + 1) * to[jd];        trees[2*jd + 1].sum += (trees[jd].r - mid) * to[jd];        to[jd] = 0;    }}void update(int jd){    trees[jd].sum = trees[2*jd].sum + trees[2 * jd + 1].sum;}void build_trees(int jd,int l,int r){    trees[jd].l=l;    trees[jd].r=r;    to[jd] = 0;    if(l==r)    {        trees[jd].sum=num[l];        return ;    }    int mid = (l+r)/2;    build_trees(jd*2,l,mid);    build_trees(jd*2+1,mid+1,r);    update(jd);}void change(int jd,int s, int t, int v){    int mid = (trees[jd].l + trees[jd].r)/2;    if(trees[jd].l >= s && trees[jd].r <= t)    {        to[jd]+=v;        trees[jd].sum += (trees[jd].r - trees[jd].l + 1) * v;        return ;    }    pushdown(jd);    if(mid >= s)        change(2*jd, s, t, v);    if(t > mid)        change(2*jd + 1,s, t, v);    update(jd);}void query(int jd ,int l,int r){    if(l<=trees[jd].l&&r >=trees[jd].r)    {        ans += trees[jd].sum;        return;    }    pushdown(jd);    int mid = (trees[jd].l+trees[jd].r)/2;    if(l<=mid) query(jd*2,l,r);    if(r>mid) query(jd*2+1,l,r);}int main(){    int n,m,l,r;    char a;    cin >> n >> m;    for(int i = 1; i <= n; i++)    {        cin >> num[i];    }    build_trees(1,1,n);    for(int i = 0; i < m; i++)    {        ans = 0;        cin >> a;        if(a == ‘Q‘)        {            cin >> l >> r;            query(1,l,r);            cout << ans << endl;        }        if(a == ‘C‘)        {            cin >> l >> r >> read;            change(1,l,r,read);        }    }    return 0;}

 


联系
我们