P8936 [JRKSJ R7] 月下缭乱 题解
min_inf
·
·
题解
老早扔进 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 即为满足要求。
```cpp
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';
}
}
```