首页 > 其他 > 详细

2018陕西省赛K题[watermelon_planting]

时间:2018-05-23 01:37:08      阅读:225      评论:0      收藏:0      [点我收藏+]

题意:有一个序列a[],描述的是另一个序列ans[]每个位置单位时间的增量。每个单位时间每个位置都会增加一个单位对应增量。时间总长m,每个单位时间包含有两种操作中的一个:1.询问ans[]在[l,r]区间的和;2.修改:a[]在[l,r]区间+1,即[l,r]区间的ans[]增量+1,a[i], n,m?≤?10^5

题解:当时脑抽没想出来,现在觉得好简单。。。考虑对每个位置,维护一个关于时间的一次函数y=a*x+b,y:是这个位置的答案,x:是时间,然后就维护两个系数a,b就可以了。维护的方法就是开两颗线段树分别维护a,b,这就是个裸的区间加,区间求和。位置i系数的表达式:a = (ai + 修改次数),b = - (修改的时间和)。随机跑了跑没啥大问题,发现问题欢迎评论区指出。(大概一辈子都是桶排选手吧。)

#include <bits/stdc++.h>
typedef long long ll;
const int N = 1e5 + 100;
using namespace std;
int n,m;
ll a[N];
struct seg{int l,r;ll sum,tag;}tree[2][N<<2];
void push_up(int p,seg* tree) {
    tree[p].sum = tree[p<<1].sum + tree[p<<1|1].sum;
}
void push_down(int p,seg* tree) {
    if(tree[p].tag) {
        tree[p<<1].sum += 1LL*(tree[p<<1].r - tree[p<<1].l + 1)*tree[p].tag;
        tree[p<<1|1].sum += 1LL*(tree[p<<1|1].r - tree[p<<1|1].l + 1)*tree[p].tag;
        tree[p<<1].tag += tree[p].tag;
        tree[p<<1|1].tag += tree[p].tag;
        tree[p].tag = 0;
    }
}
void build(int p, int l, int r, seg* tree) {
    tree[p].l = l; tree[p].r = r;
    tree[p].sum = tree[p].tag = 0;
    if(l == r) {
        tree[p].sum = a[l]; return;
    }
    int mid = (l + r) >> 1;
    build(p<<1, l, mid, tree), build(p<<1|1, mid+1, r, tree);
    push_up(p, tree);
}
void buildb(int p, int l, int r, seg* tree) {
    tree[p].l = l; tree[p].r = r;
    tree[p].sum = tree[p].tag = 0;
    if(l == r) return;
    int mid = (l + r) >> 1;
    buildb(p<<1, l, mid, tree), buildb(p<<1|1, mid+1, r, tree);
    push_up(p, tree);
}
void add(int p, int l, int r, ll x,seg* tree) {
    if(tree[p].l == l && tree[p].r ==r) {
        tree[p].sum += 1LL*(r-l+1)*x;
        tree[p].tag += x;
        return;
    }
    int mid = (tree[p].l + tree[p].r) >> 1;
    push_down(p, tree);
    if(r <= mid) add(p<<1, l, r, x, tree);
    else if(l > mid) add(p<<1|1, l, r, x, tree);
    else add(p<<1, l, mid, x, tree), add(p<<1|1, mid+1, r, x, tree);
    push_up(p, tree);
}
ll ask(int p, int l, int r,seg* tree) {
    if(tree[p].l == l && tree[p].r == r) return tree[p].sum;
    push_down(p, tree);
    int mid = (tree[p].l + tree[p].r) >> 1;
    if(r <= mid) return ask(p<<1, l, r, tree);
    else if(l > mid) return ask(p<<1|1, l, r, tree);
    else return ask(p<<1, l, mid, tree) + ask(p<<1|1, mid+1, r, tree);
}
//ll ans[N];
//void update(int l,int r){
//    for(int i=1;i<=n;++i)ans[i]+=a[i];
//    for(int i=l;i<=r;++i)++a[i];
//}
//ll ask2(int l,int r){ll res=0;
//    for(int i=1;i<=n;++i)ans[i]+=a[i];
//    for(int i=l;i<=r;++i)res+=ans[i];
//    return res;
//}
int main() {
    while(scanf("%d",&n)) {
        for(int i=1;i<=n;++i)scanf("%lld",&a[i]);//,ans[i]=0;
        build(1,1,n,tree[0]);
        buildb(1,1,n,tree[1]);
        scanf("%d",&m);
        for(int i=1;i<=m;++i) {char opt;int l,r;
            scanf(" %c %d %d",&opt,&l,&r);
            //opt=rand()%2;l=rand()%n+1,r=rand()%n+1;if(l>r)swap(l,r);
            //printf("%d : [%d,%d]\n",opt,l,r);
            if(opt==‘Q‘){
                ll ans = ask(1,l,r,tree[0])*i-ask(1,l,r,tree[1]);
                //ll ans2=ask2(l,r);
                printf("%lld\n",ans);
//                if(ans!=ans2){
//                    printf("_______________________\n");
//                }
            }
            else {
                add(1,l,r,1,tree[0]);
                add(1,l,r,i,tree[1]);
//                update(l,r);
            }
        }
    }
    return 0;
}

 

2018陕西省赛K题[watermelon_planting]

原文:https://www.cnblogs.com/RRRR-wys/p/9074789.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!