自动搬运

查看原文

来自洛谷，原作者为

	min_inf 你路过的 与我追逐的 我会等它们重合

搬运于2025-08-24 22:43:54，当前版本为作者最后更新于2024-02-20 17:30:52，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

老早扔进 to-do list 吃灰的东西拿出来做了一下，不知道为什么有紫以及为什么题解做法都这么神秘。

考虑最终的序列 $a$，对于一个位置 $i$，$\operatorname{sol}(l,r)=\operatorname{sol}(1,m)$ 时 $\exists j \in [l,r],l_j \le i \le r_j \land x_j = a_i$。

考虑枚举这个值 $j$，把所有 $a_i=j$ 的地方都提出来，对所有 $x_i=j$ 的区间双指针一遍，用线段树维护位置最小被覆盖到的次数，$\ne 0$ 即为满足要求。

$O(n \log n)$。

namespace KnownError_{
    constexpr int N = 1e6+5;
    int n,m,R[N];
    struct opt{int l,r,id;};
    vector<opt> ve[N];
    int fa[N];
    int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);}
    int mn[N<<1],tg[N<<1];
    void setp(int u,int L,int R,int x,int v,int t){
        if(L==R){mn[u]=v-t;return;}
        t+=tg[u];
        int M=L+R>>1,ls=M<<1,rs=M<<1|1;
        if(x<=M)setp(ls,L,M,x,v,t);
        else setp(rs,M+1,R,x,v,t);
        mn[u]=min(mn[ls],mn[rs])+tg[u];
    }
    void add(int u,int L,int R,int l,int r,int x){
        if(r<L||R<l||r<l)return;
        if(l<=L&&R<=r){mn[u]+=x,tg[u]+=x;return;}
        int M=L+R>>1,ls=M<<1,rs=M<<1|1;
        add(ls,L,M,l,r,x);
        add(rs,M+1,R,l,r,x);
        mn[u]=min(mn[ls],mn[rs])+tg[u];
    }
    void main(){
        cin>>n>>m;
        rep(i,1,m){
            int l,r,x;
            cin>>l>>r>>x;
            ve[x].push_back({l,r,i});
        }
        iota(R+1,R+m+1,1);
        iota(fa+1,fa+n+2,1);
        fill(mn+1,mn+2*n,1e9);
        per(i,m,1){
            vector<opt> now;
            vector<int> pt;
            for(auto o:ve[i])if(find(o.l)<=o.r)now.push_back(o);
            if(now.empty())continue;
            for(auto o:now){
                int p=find(o.l);
                while(p<=o.r){
                    pt.push_back(p);
                    fa[p]=p+1,p=find(p);
                }
            }
            for(auto j:pt)setp(1,1,n,j,0,0);
            int cnt=now.size();
            int p=0;
            repn(j,cnt){
                while(p<cnt&&!mn[1])add(1,1,n,now[p].l,now[p].r,1),++p;
                int pos=j?now[j-1].id+1:1;
                R[pos]=max(R[pos],mn[1]?now[p-1].id:m+1);
                add(1,1,n,now[j].l,now[j].r,-1);
            }
            R[now.back().id+1]=max(R[now.back().id+1],m+1);
            for(auto j:pt)setp(1,1,n,j,1e9,0);
        }
        ui ans1=0,ans2=0,ans3=0;
        rep(i,1,m){
            R[i]=max(R[i],R[i-1]);
            ui f=m-R[i]+1;
            ans1+=f;
            ans2^=f*(ui)i;
            ans3+=f*(ui)i;
        }
        cout<<ans1<<' '<<ans2<<' '<<ans3<<'\n'; 
    }
}