带修主席树

女爷i 2024-04-18 16:15 57阅读 0赞

题意：求区间内  满足x<=a\[i\]<=y的区间段的个数。[https://nanti.jisuanke.com/t/41356][https_nanti.jisuanke.com_t_41356]

使用带修主席树会T。

但是这个板子好像很好写，很好用，记下来

//solve by fcy 13:02:35
    #include<bits/stdc++.h>
    #define ll long long
    #define rep(i,a,b) for(int i=a;i<=b;i++)
    using namespace std;
    const int maxn=200010;
    struct in{
        int l,r,sum;
    }s[maxn*210];
    int a[maxn],rt[maxn],N,M,cnt;
    void add(int &Now,int L,int R,int pos,int v)
    {
        if(!Now) Now=++cnt; s[Now].sum+=v;
        if(L==R) return ;int Mid=(L+R)>>1;
        if(pos<=Mid) add(s[Now].l,L,Mid,pos,v);
        else add(s[Now].r,Mid+1,R,pos,v);
    }
    void Add(int x,int pos,int v)
    {
        while(x<=N){
            add(rt[x],1,N,pos,v);
            x+=(-x)&x;
        }
    }
    int query(int Now,int L,int R,int l,int r)
    {
        if(!Now||s[Now].sum==0) return 0;
        if(l<=L&&r>=R) return s[Now].sum;
        int Mid=(L+R)>>1,res=0;
        if(l<=Mid) res+=query(s[Now].l,L,Mid,l,r);
        if(r>Mid) res+=query(s[Now].r,Mid+1,R,l,r);
        return res;
    }
    int Query(int x,int L,int R)
    {
        if(L>R||x==0) return 0;
        int res=0; while(x){
            res+=query(rt[x],1,N,L,R);
            x-=(-x)&x;
        } return res;
    }
    void read(int &x){
        x=0; char c=getchar();
        while(c>'9'||c<'0') c=getchar();
        while(c>='0'&&c<='9') x=x*10+c-'0',c=getchar();
    }
    int main()
    {
        scanf("%d%d",&N,&M);
        rep(i,1,N) {
            read(a[i]);
            if(a[i]!=a[i-1]) Add(i,a[i],1);
        }
        int opt,pos,L,R,x,y;
        while(M--){
            read(opt);
            if(opt==2){
                read(L); read(R); read(x); read(y);
                int ans=Query(R,x,y)-Query(L-1,x,y);
                //if(a[L]!=a[L-1]&&(a[L]<=y&&a[L]>=x)) ans--;
                if(a[L]==a[L-1]&&a[L]<=y&&a[L]>=x) ans++;
                printf("%d\n",ans);
            }
            else {
                read(pos); read(x);
                if(a[pos]==x) continue;
                if(a[pos]!=a[pos-1]) Add(pos,a[pos],-1);
                if(pos+1!=N&&a[pos+1]!=a[pos]) Add(pos+1,a[pos+1],-1);
                a[pos]=x;
                if(a[pos]!=a[pos-1]) Add(pos,a[pos],1);
                if(pos+1!=N&&a[pos+1]!=a[pos]) Add(pos+1,a[pos+1],1);
            }
        }
        return 0;
    }

[https_nanti.jisuanke.com_t_41356]: https://nanti.jisuanke.com/t/41356