序列

发表于 |
字数统计: 218 | 阅读时长 ≈ 1
  • Code Level: ※
  • Thinking Level: ※

Description

给一个长n的全0序列进行如下操作：

  1. 给[l,r]加上1
  2. 重复[l,r]的操作（操作保证合法）

求最终 a[n]

Solution

从后往前维护差分

Details

  • 逆向思维
  • 差分的逆推

Code

1
2
3
4
5
6
7
8
9
10
11
#include<bits/stdc++.h>
using namespace std;
const int nn=100005;
const int mo=1e9+7;
int n,q,a[nn],s[nn];struct atl{int x,y,z;}e[nn];
int main(){
    int i;scanf("%d%d",&n,&q); for(i=1;i<=q;i++)scanf("%d%d%d",&e[i].x,&e[i].y,&e[i].z); a[n+1]=0; s[q+1]=1;
    for(i=q;i>0;i--){ s[i]+=s[i+1]; if(e[i].x==1) a[e[i].y-1]-=s[i],a[e[i].z]+=s[i]; else s[e[i].y-1]-=s[i],s[e[i].z]+=s[i]; }
    for(i=n;i>0;i--) a[i]=((a[i]+a[i+1])%mo+mo)%mo; for(i=1;i<=n;i++) printf("%d ",a[i]);
    return 0;
}