rt,可过 $\text{CF896E}$ 但不可过本题QwQ

CF评测记录

本题评测记录

#include <bits/stdc++.h>

#define rep(i,l,r) for (int i = l; i <= r; i++)
#define per(i,r,l) for (int i = r; i >= l; i--)
#define fi first
#define se second
#define prt std::cout
#define gin std::cin
#define edl std::endl

namespace wxy{

const int N = 1e6+10,T = 5e5+10,M = 5e5+10;

int n,m,cS,S,a[N],ans[N],fa[N],size[T],b[N];

int st[T],rev[N];

struct node{int op,l,r,x;}ask[M];

inline int read(){
    int s=0,f=1;char ch=getchar();
    while(!isdigit(ch)) {if(ch=='-') f=-1;ch=getchar();}
    while(isdigit(ch)) s=s*10+ch-'0',ch=getchar();
    return s*f;
}

inline void write(int x){
    if(x < 0)putchar('-'),x = -x;
    if(x > 9)write(x / 10);
    putchar(x % 10 + '0');
}

inline int getL(int idx){return (idx-1)*S+1;}
inline int getR(int idx){return std::min(n,idx*S);} 

int get(int x){return fa[x] == x ? x : fa[x] = get(fa[x]);}
inline void merge(int x,int y){
    //x to y
    if (st[x] == 0) return;
    if (st[y] == 0) {st[y] = st[x]; rev[st[y]] = y;}
    else {fa[st[x]] = st[y];}
    size[y] += size[x]; st[x] = size[x] = 0;
}

inline void build(int L,int R){
    rep(i,L,R){
        if (st[a[i]]) {fa[i] = st[a[i]];}
        else {st[a[i]] = i; fa[i] = i; rev[i] = a[i];}
        size[a[i]]++;
    }
}

//清空并查集森林根节点的数据和查询位置上的值
inline void rebuild(int L,int R,int l,int r,int x,int &tag,int &minv,int &maxv){
    minv = 0,maxv = 0; 
    rep(i,L,R){
        a[i] = rev[get(i)] - tag;
        if (a[i] > x && i >= l && i <= r) a[i] -= x;
        maxv = std::max(maxv,a[i]); minv = std::min(minv,a[i]);
    }
    rep(i,L,R) {st[rev[get(i)]] = size[rev[get(i)]] = 0;}
    build(L,R); 
    tag = 0;
}

inline void solve(int x){
    int L = getL(x),R = getR(x),tag = 0,minv = 0,maxv = 0; 
    memset(st,0,sizeof st);  memset(size,0,sizeof size);
    rep(i,L,R) {maxv = std::max(maxv,a[i]); minv = std::min(minv,a[i]);}
    build(L,R); 
    rep(i,1,m){
        if (ask[i].l <= L && ask[i].r >= R){
            //prt << i << " ";
            int y = ask[i].x + tag;
            if (ask[i].op == 2) {ans[i] += size[y]; continue;}
            if (y >= maxv) continue;
            if (maxv <= ask[i].x + y){
                rep(j,y+1,maxv) merge(j,j-ask[i].x);
                maxv = y;
            }else{
                tag += ask[i].x;
                rep(j,minv,y) merge(j,j+ask[i].x); 
                minv += ask[i].x;
            }
        }else if (b[ask[i].l] != b[ask[i].r] && b[ask[i].l] == x){
            //prt << i << " ";
            if (ask[i].op == 2){
                int y = ask[i].x;
                rep(j,ask[i].l,R) ans[i] += (rev[get(j)]-tag==y);
                continue;
            }
            rebuild(L,R,ask[i].l,ask[i].r,ask[i].x,tag,minv,maxv);
        }else if (b[ask[i].l] != b[ask[i].r] && b[ask[i].r] == x){
            //prt << i << " ";
            if (ask[i].op == 2){
                int y = ask[i].x;
                rep(j,L,ask[i].r) ans[i] += (rev[get(j)]-tag==y);
                continue;
            }
            rebuild(L,R,ask[i].l,ask[i].r,ask[i].x,tag,minv,maxv);
        }else if (b[ask[i].l] == b[ask[i].r] && b[ask[i].l] == x){
            //prt << i << " ";
            if (ask[i].op == 2){
                int y = ask[i].x;
                rep(j,ask[i].l,ask[i].r) ans[i] += (rev[get(j)]-tag==y);
                continue;
            }
            rebuild(L,R,ask[i].l,ask[i].r,ask[i].x,tag,minv,maxv);
        }
    }
    
}

inline void main(){
    #ifndef ONLINE_JUDGE
        freopen("in.in","r",stdin);
        freopen("out.out","w",stdout);
    #endif
    n = read(); m = read(); S = 1000; cS = (n-1) / S + 1;
    rep(i,1,n) b[i] = (i-1)/S+1;
    rep(i,1,n) a[i] = read();
    rep(i,1,m){
        ask[i].op = read(); ask[i].l = read(); 
        ask[i].r = read(); ask[i].x = read();
    }
    rep(i,1,cS) solve(i); 
    rep(i,1,m)  if (ask[i].op == 2) {write(ans[i]); puts("");}
}

}signed main(){wxy::main(); return 0;}