筱玛爱线段树
筱玛爱线段树
https://ac.nowcoder.com/acm/problem/25737
分析
我们主要考虑如何处理 的操作又重新做一次,这个我们考虑区间加,定义 为第 次操作要执行的次数。那么这个我们可以通过差分做到。最后处理区间加。这个一样可以用差分来做,那么最后的复杂度为 。
- 差分,我们定义数组 ,如果原值为 。那么满足 。那么给 全部 等同于 。这样我们对于区间加就可以直接修改两个点来操作了。
代码
#include<bits/stdc++.h> using namespace std; int read() { int x=0,f=0;char ch=getchar(); while(!isdigit(ch)) {if(ch=='-')f=1;ch=getchar();} while(isdigit(ch)) {x=x*10+ch-'0';ch=getchar();} return f?-x:x; } const int N = 1e5 + 100,inf = 0x3f3f3f3f,mod = 1e9 + 7; int A[N],L[N],R[N],C[N],ans[N],n,m; void del(int &x,int y) {x -= y;if(x<0)x+=mod;} void upd(int &x,int y) {x += y;if(x>=mod)x-=mod;} int main() { n = read();m = read(); for(int i = 1;i <= m;i++) A[i] = read(),L[i] = read(),R[i] = read(); for(int i = m;i >= 1;i--) { upd(C[i],C[i+1]); if(A[i] == 2) del(C[L[i] - 1],C[i] + 1),upd(C[R[i]],C[i] + 1); if(A[i] == 1) del(ans[R[i] + 1],C[i] + 1),upd(ans[L[i]],C[i] + 1); } int now = 0; for(int i = 1;i <= n;i++) { upd(now,ans[i]); printf("%d ",now); } printf("\n"); return 0; }