Greg and Array

Codeforces Round #179 (Div. 2) C:http://codeforces.com/problemset/problem/296/C

题意：给你一个序列，然后有两种操作，第一种操作是区间加上一个数，第二种操作也是区间操作 1 3 但是这里的区间不是对原序列，而是指第一种操作，1 3，表示把1,2,3三种操作都执行一遍。求所有的操作结束之后原来数组的数。

题解：先考虑一个简单的问题，就是只有第一种操作，就是区间加上一个数。这里没有查询，所以，先加和后加没有区别。所以或一个图就可以知道。我们可以这么搞，用一个vector<int>ll[n],rr[N],ll[i]记录以i为左端更新的那种操作，rr[i]表示以i为右端点的那些更新，as 表示当前数最终应该加的值，当遇到以i开始的时候，as+=这个更新的值，遇到i结尾的时候，as-=这个更新值，这样就可以for一遍就可以了。这样就解决的这个简单的问题，现在来考虑这个题目，也就是二级操作，同理，二级操作也可以了采用这种方式，来统计数操作执行的次数，然后就转化成一级问题，不过此时一级操作的更新值变为原来的值*执行的次数。

 #include<cstdio>

 #include<cstring>

 #include<iostream>

 #include<algorithm>

 #include<vector>

 using namespace std;

 const int N=1e5+;

 long long a[N],b[N],c[N];

 int n,m,k;

 vector<int>ll[N],rr[N],l[N],r[N];

 struct Node{

   int l,r;

   long long val;

 }num[N],temp[N];

 int t1,t2;

 int main(){

    while(~scanf("%d%d%d",&n,&m,&k)){

       memset(a,,sizeof(a));

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

         scanf("%I64d",&a[i]);

       }

       for(int i=;i<=m;i++){

         scanf("%d%d%I64d",&num[i].l,&num[i].r,&b[i]);

         ll[num[i].l].push_back(i);

         rr[num[i].r].push_back(i);

         num[i].val=;

       }

       for(int i=;i<=k;i++){

          scanf("%d%d",&temp[i].l,&temp[i].r);

          l[temp[i].l].push_back(i);

          r[temp[i].r].push_back(i);

       }

       long long as=;

       memset(c,,sizeof(c));

       for(int i=;i<=m;i++){

           as+=l[i].size();

           c[i]+=as;

           as-=r[i].size();

       }

       for(int i=;i<=m;i++){

          num[i].val=c[i]*b[i];

       }

        as=;

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

          for(int j=;j<ll[i].size();j++)

             as+=num[ll[i][j]].val;

             a[i]+=as;

           for(int j=;j<rr[i].size();j++)

             as-=num[rr[i][j]].val;

             if(i!=n)

            printf("%I64d ",a[i]);

       }

       printf("%I64d\n",a[n]);

    }

 }

巴特西

Greg and Array

最新文章

热门文章