筱玛爱线段树

筱玛爱线段树

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;
}
全部评论

相关推荐

Hello_WordN:咱就是说,除了生命其他都是小事,希望面试官平安,希望各位平时也多注意安全
点赞 评论 收藏
分享
11 3 评论
分享
牛客网
牛客企业服务