标签： hson Set int tot ms id
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+3,INF=1e9;
int n,m,q,tot,col[N],hson[N],sz[N],fa[N],res[N],num[N],pos[N],cur[N],ans[N];
struct Set
{
int r,id;
friend bool operator <(Set a,Set b){return a.r!=b.r?a.r<b.r:a.id<b.id;}
};
set<Set>now;
set<ll>in[N];
multiset<Set>ms[N];
vector<ll>ve[N],val[N];
struct Nod
{
int l,r,id;
friend bool operator <(Nod a,Nod b){return a.l!=b.l?a.l>b.l:a.r<b.r;}
}a[N];
void Add(int x,int y,int z)
{
auto t=ms[x].lower_bound(Set{y,0});
if(t==ms[x].end()||t->r!=y)res[x]++;
ms[x].insert(Set{y,z});
}
void Del(int x,int y,int z)
{
ms[x].erase(ms[x].lower_bound(Set{y,0}));
auto t=ms[x].lower_bound(Set{y,z});
if(t==ms[x].end()||t->r!=y)res[x]--;
}
void Merge(int x)
{
//if(x==63)cout<<res[hson[x]]<<endl;
num[x]=num[hson[x]];pos[num[x]]=x;
for(int y:ve[x])if(y!=hson[x])
{
for(Set z:ms[num[y]])
{
Add(num[x],z.r,z.id),cur[z.id]=num[x];
}
}
//if(x==63)cout<<res[hson[x]]<<endl;
}
void Tuopu()
{
queue<int>qu;
for(int i=m+1;i<=tot;i++)if(in[i].empty())qu.push(i);
while(!qu.empty())
{
int x=qu.front(),y=fa[x];qu.pop();
if(!y)
{
for(Set z:ms[num[x]])cur[z.id]=0;
ms[num[x]].clear();continue;
}
if(!(--in[y]))
{
Merge(y);
//if(y==63)cout<<res[num[y]]<<" "<<a[y].r-a[y].l+1<<" "<<a[y].id<<endl;
if(a[y].r-a[y].l+1==res[num[y]])qu.push(y),ans[a[y].id]=0;
}
}
}
void Work(int st,int w)
{
if(a[st].r-a[st].l+1!=res[num[st]])return;
queue<int>qu;qu.push(st);ans[a[st].id]=min(ans[a[st].id],w);
while(!qu.empty())
{
int x=qu.front(),y=fa[x];qu.pop();
if(!y)
{
for(Set z:ms[num[x]])cur[z.id]=0;
ms[num[x]].clear();continue;
}
if((--in[y])<=0)Merge(y);
if(a[y].r-a[y].l+1==res[num[y]])qu.push(y),ans[a[y].id]=min(ans[a[y].id],w);
//if(ans[9]>0)cout<<st<<" "<<w<<endl;
}
}
int main()
{
freopen("artist.in","r",stdin);
freopen("artist.out","w",stdout);
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cin>>n>>m>>q;tot=m;
for(int i=1;i<=n;i++)cin>>col[i];
for(int i=1;i<=m;i++)cin>>a[i].l>>a[i].r,a[i].id=i;
sort(a+1,a+m+1);
for(int i=1;i<=m;i++)
{
set<Set>delw;ll x=0;ans[i]=INF;
for(Set t:now)
{
if(t.r>a[i].r)continue;
else delw.insert(t),ve[i].push_back(t.id),x+=t.r-a[t.id].l+1;
}
ll las=a[i].l;tot++;hson[i]=tot;sz[tot]=a[i].r-a[i].l+1-x;fa[tot]=i;
ve[i].push_back(tot);in[i]++;
for(Set t:delw)
{
for(int j=las;j<a[t.id].l;j++)cur[j]=tot,Add(tot,col[j],j),val[tot].push_back(j);
now.erase(now.find(Set{t.r,t.id}));las=t.r+1;in[i]++;fa[t.id]=i;
if(sz[t.id]>sz[hson[i]])hson[i]=t.id;
}
for(int j=las;j<=a[i].r;j++)cur[j]=tot,Add(tot,col[j],j),val[tot].push_back(j);
sz[i]=a[i].r-a[i].l+1;now.insert(Set{a[i].r,i});
//if(cur[29]>0)cout<<tot<<endl;
}
for(int i=1;i<=tot;i++)num[i]=i,pos[i]=i;
Tuopu();cout<<res[136]<<endl;
for(int t=1;t<=q;t++)
{
int x,y,z;cin>>x>>y;z=cur[x];
if(44<=x&&x<=47)cout<<t<<" "<<x<<" "<<z<<" "<<res[z]<<endl;
if(!z)continue;
Del(z,col[x],x);col[x]=y;Add(z,col[x],x);
Work(pos[z],t);
if(res[136]!=3)cout<<x<<" "<<t<<" "<<z<<" "<<res[136]<<endl;
}
for(int i=1;i<=m;i++)cout<<(ans[i]==INF?m+i:ans[i])<<endl;
ll s=0;
for(int i=1;i<=m;i++)s^=ans[i]==INF?m+i:ans[i];
cout<<s;
}
标签：,
hson,
Set,
int,
tot,
ms,
id
From： https://www.cnblogs.com/Hanghang007/p/17742627.html