Curious Array Codeforces - 407C(高阶差分(?)) || sequence

https://codeforces.com/problemset/problem/407/C

（自用,勿看）

手模一下找一找规律，可以发现，对于一个修改(l,r,k)，相当于在[l,r]内各位分别加上[1,0,0,0,0,..]做k+1次前缀和得到的数组

比如(l=3,r=6,k=2)，[1,0,0,..]做k+1=3次前缀和后为[1,3,6,10,15,..]，因此这次修改相当于a[l]+=1,a[l+1]+=3,a[l+2]+=6,a[l+3]+=10

很容易想到k从大到小排序，用差分维护，不断做前缀和“解包”（不展开写了..）

然后我就不会了。。因为每一次是“区间加”，我只能做到从某个位置到末尾全部加，没有办法把多余的消掉

膜了大佬，发现只要每一层差分的时候都在合适位置减去合适值就行了，找规律（例如l=3,r=6,k=2，一开始是1,0,0,0,-1，第一次变成1,1,1,1,0，再变成1,1,1,1,-4，第二次变成1,2,3,4,0，再变成1,2,3,4,-10，第三次变成1,3,6,10,0）（考虑第p次，[1,0,0,0..]做p+1次前缀和得到数组c，那么在r+1位置处减去c[r-l+1]，第0次（即第1次开始前）也要减）

然后多个同一阶的差分数列可以直接相加，因此就有了O((n+m)k)的做法

 #include<cstdio>

 #include<algorithm>

 #include<cstring>

 #include<vector>

 using namespace std;

 #define fi first

 #define se second

 #define mp make_pair

 #define pb push_back

 typedef long long ll;

 typedef unsigned long long ull;

 typedef pair<ll,ll> pll;

 const ll md=;

 ll n,m;

 vector<pll> a1[];

 ll an[][];

 ll tt[][];//tt[i]是对1,0,0,0,..做i+1次前缀和得到的数组

 ll a[];

 int main()

 {

     ll i,j,k,x,y,z;pll t;

     scanf("%lld%lld",&n,&m);

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

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

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

         tt[][i]=;

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

     {

         for(j=;j<=n;j++)

         {

             tt[i][j]=(tt[i][j-]+tt[i-][j]);

             (tt[i][j]>=md) && (tt[i][j]-=md);

             //printf("at%lld %lld %lld\n",i,j,tt[i][j]);

         }

     }

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

     {

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

         a1[z].pb(mp(x,y));

     }

     for(i=;i>=;i--)

     {

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

         {

             x=a1[i][j].fi;y=a1[i][j].se;

             ++an[i][x];

             (an[i][x]>=md) && (an[i][x]-=md);

             ++y;

             for(k=i;k>=;k--)

             {

                 an[k][y]-=tt[i-k][y-x];

                 //printf("2t%lld %lld %lld\n",i-k,y-x,tt[i-k][y-x]);

                 //printf("1t%lld %lld %lld\n",k,y,tt[i-k][y-x]);

                 (an[k][y]<) && (an[k][y]+=md);

             }

         }

         for(k=;k<=n;k++)

         {

             an[i][k]+=an[i][k-];

             (an[i][k]>=md) && (an[i][k]-=md);

         }

         if(i!=)

         {

             for(k=;k<=n;k++)

             {

                 an[i-][k]+=an[i][k];

                 (an[i-][k]>=md) && (an[i-][k]-=md);

             }

         }

         //printf("1t%lld\n",i);

         //for(k=1;k<=n;k++)

         //    printf("%lld ",an[i][k]);

         //puts("");

     }

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

     {

         a[i]+=an[][i];

         (a[i]>=md) && (a[i]-=md);

     }

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

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

     return ;

 }

http://210.33.19.103/contest/1025

A题(sequence)同此题

巴特西

Curious Array Codeforces - 407C(高阶差分(?)) || sequence

最新文章

热门文章