筱玛爱线段树

筱玛爱线段树

https://ac.nowcoder.com/acm/problem/25737

操作二可真是太毒瘤了...可以一直嵌套嵌套嵌套

能不能对操作二进行差分呢??当然可以

而且有一个很重要的性质,前面的操作二不会影响后面的操作二

所以从后往前看所有操作二,对操作在树状数组上差分

为什么在树状数组上?因为可以直接查询此时操作需要执行几次

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=2e5+10; 
const int mod=1e9+7;
int l[maxn],r[maxn],top,type[maxn];
int zhi[maxn],a[maxn],n,m,ok[maxn];
int lowbit( int x ){ return x&(-x); }
int ask(int x)
{
    int ans=0;
    for(;x;x-=lowbit(x))    ans = ( ans+ok[x] )%mod;
    return ans; 
}
void add(int x,int k)
{
    for(;x<=m;x+=lowbit(x))    ok[x] = ( ok[x]+k )%mod;    
}
signed main()
{
    cin >> n >> m;
    for(int i=1;i<=m;i++)
        scanf("%lld%lld%lld",&type[i],&l[i],&r[i]);
    for(int i=m;i>=1;i--)
        if( type[i] == 2 )
        {
            int x=ask( i );
            add(l[i],x+1); add(r[i]+1,-x-1);
        }
    for(int i=1;i<=m;i++)    a[i]=ask(i);
    for(int i=1;i<=m;i++)
        if( type[i] ==1 )
        {
            zhi[l[i]]+=a[i]+1;    a[l[i]]%=mod;
            zhi[r[i]+1]-=a[i]+1;    a[r[i]+1]%=mod;
        }    
    for(int i=1;i<=n;i++)
        zhi[i] = ( zhi[i]+zhi[i-1] )%mod;
    for(int i=1;i<=n;i++)    cout << (zhi[i] % mod + mod) % mod << " "; 
}
全部评论

相关推荐

若怜君欢:驾驶证去掉吧,PPT啥的也去掉,本硕课程去掉,导师和研究方向去掉;加入本硕排名(好才写);技能栏加入你会的那些控制算法和滤波算法,这个比你会啥啥啥软件更有用;获奖写上去,奖学金啊,有没有专利啊之类的 电机和硬件这一块,属于传统制造业,制造业实习并不多。多投一些攒攒经验,有实习最好,没有也不需要焦虑(制造业实习其实除了转正,没多大用处) 最后,划重点,等秋招开始后,把你所有社交软件都发一份简历上去,并经常更新,找人内推你!
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
05-01 13:13
ecece:这么明目张胆虚报就业率啊
点赞 评论 收藏
分享
评论
1
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务