题解：P5511 决战

· · 题解

大家好，我非常喜欢暴力数据结构，所以我用分块通过了这道题目。

我们发现我们不可能直接对原序列分块，因为原序列的长度高达 10^9，根本存不下。

但是如果我们把相同的数维护成一段，每次增加的段数是 O(1) 的，这启示我们把原序列维护成很多个段，然后对这些段分块。这个时候，每个块里面维护的是很多个段，然后我们就可以进行操作了。

首先先看一下 1 操作，一看非常经典，如果 n 没有这么大的话，我们只要再维护排过序的块就行。其实现在也是一样的，我们只要对于每个块维护一个按照值排序的块，询问的时候二分就行了。

还有一个问题，我们维护了很多个段，但是问的是数的个数，所以我们还要维护一个排过序的块的每段数的个数的前缀和，然后就没有问题了。

剩下两个操作其实是比较像的，我们可以采用传统操作，散块直接改，整块打标记，打标记其实不是很难打。拿操作 2 举个例子，我们先把区间大于 2 的改成 2，再把区间大于 3 的改成 3，那其实后面那个是没用的。再比如，我们把区间小于 4 的改成 4，再把区间大于 3 的改成 3，其实前面那个就相当于小于 3 的改成 3。所以得出结论：两个标记都要对 h 取最小值。

同理我们也可以得出操作 3 就是取最大值，但是，真的做完了吗？

思考一下我们怎样进行这三个操作的，我们发现我们需要像珂朵莉树一样，把颜色段裂开进行操作。但是在裂开的过程中块内元素个数会增加，所以我们需要像块状链表一样，如果块长大于一定值，直接把它裂成两个，来稳定我们的复杂度。当然其实不用写链表，你直接加在后面，到时候全扫一遍判断即可。

时间复杂度 O(m \sqrt {m \log m})，可以通过本题。这里块长取的 137，阈值是 1.37 倍的块长。

#include<bits/stdc++.h>
#define N 100005
#define B 137
using namespace std;
struct node{
    int l,r,k;
};
bool operator<(node a,node b){
    return a.k<b.k;
}
int len[N],dy[N],xy[N],Len,inf=2e9;
node a[N/B*4][B*3],b[N/B*4][B*3];
int c[N/B*4][B*3];
int bl(int x){
    return a[x][1].l;
}
int br(int x){
    return a[x][len[x]].r;
}
int findblock(int x){
    for(int i=1;i<=Len;++i){
        if(bl(i)<=x&&x<=br(i))return i;
    }
    return -1;
}
void pushdown(int x,int op=1){
    for(int i=1;i<=len[x];++i){
        if(a[x][i].k<xy[x])a[x][i].k=xy[x];
        if(a[x][i].k>dy[x])a[x][i].k=dy[x];
        b[x][i]=a[x][i];
    }
    xy[x]=-inf;dy[x]=inf;
    if(op){
        sort(b[x]+1,b[x]+len[x]+1);
        c[x][0]=0;
        for(int i=1;i<=len[x];++i)c[x][i]=c[x][i-1]+b[x][i].r-b[x][i].l+1;
    }
}
int split(int x){
    int qwq=findblock(x);
    for(int i=1;i<=len[qwq];++i){
        if(a[qwq][i].l==x)return i;
        if(a[qwq][i].l<x&&x<=a[qwq][i].r){
            pushdown(qwq,0);len[qwq]++;
            for(int j=len[qwq];j>i;--j)a[qwq][j]=a[qwq][j-1];
            a[qwq][i].r=x-1;a[qwq][i+1].l=x;
            pushdown(qwq);return i+1;
        }
    }
    return 0;
}
void boom(int x){
    if(len[x]>=1.37*B){
        ++Len;int rr=0;
        for(int i=len[x]/2+1;i<=len[x];++i)a[Len][++rr]=a[x][i];
        len[Len]=len[x]-len[x]/2;dy[Len]=dy[x];xy[Len]=xy[x];len[x]/=2;
        pushdown(x);
        pushdown(Len);
    }
}
void updmin(int l,int r,int h){
    int L=split(l),R=split(r+1);
    int ll=findblock(l),rr=findblock(r+1);
    if(ll==rr){
        pushdown(ll,0);
        for(int i=L;i<R;++i)if(a[ll][i].k<h)a[ll][i].k=h;
        pushdown(ll);
    }
    else{
        pushdown(ll,0);
        for(int i=L;i<=len[ll];++i)if(a[ll][i].k<h)a[ll][i].k=h;
        pushdown(ll);
        pushdown(rr,0);
        for(int i=1;i<R;++i)if(a[rr][i].k<h)a[rr][i].k=h;
        pushdown(rr);
        for(int i=1;i<=Len;++i){
            if(l<=bl(i)&&br(i)<=r&&i!=ll&&i!=rr)xy[i]=max(xy[i],h),dy[i]=max(dy[i],h);
        }
    }
    boom(ll);boom(rr);
}
void updmax(int l,int r,int h){
    int ll=findblock(l),rr=findblock(r+1);
    int L=split(l),R=split(r+1);
    if(ll==rr){
        pushdown(ll,0);
        for(int i=L;i<R;++i)if(a[ll][i].k>h)a[ll][i].k=h;
        pushdown(ll);
    }
    else{
        pushdown(ll,0);
        for(int i=L;i<=len[ll];++i)if(a[ll][i].k>h)a[ll][i].k=h;
        pushdown(ll);
        pushdown(rr,0);
        for(int i=1;i<R;++i)if(a[rr][i].k>h)a[rr][i].k=h;
        pushdown(rr);
        for(int i=1;i<=Len;++i){
            if(l<=bl(i)&&br(i)<=r&&i!=ll&&i!=rr)xy[i]=min(xy[i],h),dy[i]=min(dy[i],h);
        }
    }
    boom(ll);boom(rr);
}
int query(int l,int r,int h){
    int ll=findblock(l),rr=findblock(r+1);
    int L=split(l),R=split(r+1),ans=0;
    if(ll==rr){
        pushdown(ll,0);
        for(int i=L;i<R;++i)ans+=(a[ll][i].k<h)*(a[ll][i].r-a[ll][i].l+1);
        pushdown(ll);
    }
    else{
        pushdown(ll,0);
        for(int i=L;i<=len[ll];++i)ans+=(a[ll][i].k<h)*(a[ll][i].r-a[ll][i].l+1);
        pushdown(ll);
        pushdown(rr,0);
        for(int i=1;i<R;++i)ans+=(a[rr][i].k<h)*(a[rr][i].r-a[rr][i].l+1);
        pushdown(rr);
        for(int i=1;i<=Len;++i){
            if(l<=bl(i)&&br(i)<=r&&i!=ll&&i!=rr){
                if(h<=xy[i])continue;
                if(h>dy[i]){
                    ans+=br(i)-bl(i)+1;continue;
                }
                int ul=1,ur=len[i],aans=0;
                while(ul<=ur){
                    int mid=(ul+ur)>>1;
                    if(b[i][mid].k<h)aans=mid,ul=mid+1;
                    else ur=mid-1;
                }
                ans+=c[i][aans];
            }
        }
    }
    boom(ll);boom(rr);
    return ans;
}
int n,m,zx,yhb;
signed main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    //freopen("data.in","r",stdin);
    //freopen("data.out","w",stdout);
    cin>>n>>m>>zx;len[++Len]=1;
    a[Len][1]=b[Len][1]={1,n+n,0};xy[Len]=-inf;dy[Len]=inf;
    while(m--){
        int op,l,r,h;cin>>op>>l>>r>>h;
        if(zx)l^=yhb,r^=yhb,h^=yhb;
        if(l>r)continue;
        if(op==1)yhb=query(l,r,h),cout<<yhb<<'\n';  
        else if(op==2)updmax(l,r,h);
        else updmin(l,r,h);
        //print();
    }
    return 0;
}