64MB,1.5s
题目描述
您正在欣赏 galgame 的 HS，然后游戏崩溃了，于是您只能做数据结构题了：
维护一个长为 \(n\) 的序列 \(a_i\)，有 \(m\) 次操作。
-
将区间 \([l,r]\) 的值修改为 \(x\)。
-
询问区间 \([l,r]\) 出现了多少种不同的数，也就是说同一个数出现多次只算一个。
输入格式
第一行两个整数 \(n,m\)。
第二行 \(n\) 个整数表示 \(a_i\)。
后面 \(m\) 行每行为 \(1\ l\ r\ x\) 或者 \(2\ l\ r\) ，分别表示修改和询问。
输出格式
对于每个询问，输出一个数表示答案。
样例 #1
样例输入 #1
5 5
1 2 3 4 5
2 1 5
1 2 3 4
2 1 5
2 3 3
2 2 4
样例输出 #1
5
3
1
1
\(1\leq n , m \leq 10^5\)，\(1\leq a_i\leq 10^9\)。
数颜色不带修的时候，维护每一种颜色上一次的出现地方 \(ls_i\)，对着 \(r\) 扫描线，当 新扫到一个 \(a_i\) 时把树状数组中 \(ls_{a_i}\) 那个地方改掉，把 \(i\) 赋值为 1，询问时后缀查询。
还有一种理解方式：如果一个数 \(i\) 上一次出现在 \(ls\)，那么数的时候也就是数有多少个满足 \(l\le i\le r,ls<i\) 的点对。
那么回到原题，只有区间覆盖，可以考虑用 ODT ，然后现在是某一个区间 \([l,r]\) 都是 \(c\)，如果 \(c\) 的上一次出现在 ls，那么可以插一个在 \(( ls,l)\) 的价值为 1 的点，插一个在 \((r+1,r)\) 的价值为 -1 的店。
但是可能会把某一个点对删除，所以要增加时间维，在删去时插一个在这个时间把这个点删去的点。
那么在 \(t\) 时刻的询问 \(l,r\) 就是把时间维不超过 \(t\)，第一位不超过 \(l\)，第二维不超过 \(r\) 的店的价值之和就是颜色数，可以用 CDQ 统计。
然后发现你超时了？把 CDQ 的排序改成归并。
然后发现你 MLE 了？ l,r,t 都不超过 1e6,可以压成一个 long long.
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
bool fir;
int n,m,c,ans[N],k,tr[N];
struct node{
int l,r,w;
bool operator<(const node&n)const{
return l<n.l;
}
};
struct hjhakioi{
long long k;
bool operator<(const hjhakioi&q)const{
if((k>>20&1048575)^(q.k>>20&1048575))
return (k>>20&1048575)<(q.k>>20&1048575);
return (k>>60)-1&&(q.k>>60)==1;
}
}qu[N*19];
set<node>s;
set<pair<int,int> >t[N<<1];
map<int,int>mp;
bool sec;
void upd(int x,int y)
{
for(;x<=n;x+=x&-x)
tr[x]+=y;
}
int ask(int x)
{
int ret=0;
for(;x;x-=x&-x)
ret+=tr[x];
return ret;
}
void query(int x,int y,int t,int op)
{
qu[++k]=(hjhakioi){(1LL*x<<40LL)^(1LL*y<<20LL)^t^(op+1LL<<60)};
}
void add(int l,int r,int tm,int c)
{
set<pair<int,int> >::iterator it=t[c].lower_bound(make_pair(l,r));
if(it!=t[c].end())
{
int ls=1;
if(it!=t[c].begin())
{
--it;
ls=it->second+1;
++it;
}
query(ls,it->first,tm,-1);
query(r+1,it->first,tm,1);
}
int ls=1;
if(it!=t[c].begin())
{
--it;
ls=it->second+1;
}
query(ls,l,tm,1);
query(r+1,r,tm,-1);
t[c].insert(make_pair(l,r));
s.insert((node){l,r,c});
}
void del(int l,int r,int tm,int c)
{
set<pair<int,int> >::iterator it=t[c].upper_bound(make_pair(l,r)),i;
if(it!=t[c].end())
{
int ls=1;
i=it;
query(r+1,it->first,tm,-1);
--it;
if(it!=t[c].begin())
{
--it;
ls=it->second+1;
++it;
}
++it;
query(ls,it->first,tm,1);
}
--it;
int ls=1;
if(it!=t[c].begin())
{
--it;
ls=it->second+1;
++it;
}
query(ls,l,tm,-1);
query(r+1,r,tm,1);
t[c].erase(make_pair(l,r));
s.erase((node){l,r,c});
}
set<node>::iterator split(int x,int t)
{
set<node>::iterator it=s.lower_bound((node){x,0,0});
if(it!=s.end()&&it->l==x)
return it;
--it;
int l=it->l,r=it->r,w=it->w;
del(l,r,t,w);
add(l,x-1,t,w);
add(x,r,t,w);
return s.lower_bound((node){x,r,w});
}
void solve(int l,int r,int x,int y)
{
if(x>y)
return;
if(l^r)
{
int md=l+r>>1,k=y+1;
for(int i=x;i<=y;i++)
if((qu[i].k&1048575)>md)
k=i,i=y;
solve(l,md,x,k-1);
solve(md+1,r,k,y);
inplace_merge(qu+x,qu+k,qu+y+1);
}
sort(qu+x,qu+y+1);
int md=l+r>>1;
for(int i=x;i<=y;i++)
{
if(1==(qu[i].k>>60)&&(qu[i].k&1048575)>md)
ans[qu[i].k&1048575]+=ask(qu[i].k>>40&1048575);
if(1^(qu[i].k>>60)&&(qu[i].k&1048575)<=md)
upd(qu[i].k>>40&1048575,(qu[i].k>>60)-1);
}
for(int i=x;i<=y;i++)
if(1^(qu[i].k>>60)&&(qu[i].k&1048575)<=md)
upd(qu[i].k>>40&1048575,1-(qu[i].k>>60));
}
void write(int x)
{
if(!x)
return;
write(x/10);
putchar(x%10+48);
}
int read()
{
int s=0;
char ch=getchar();
while(ch<'0'||ch>'9')
ch=getchar();
while(ch>='0'&&ch<='9')
s=s*10+ch-48,ch=getchar();
return s;
}
int main()
{
memset(ans,-1,sizeof(ans));
scanf("%d%d",&n,&m);
for(int i=1,x;i<=n;i++)
{
if(!mp[x=read()])
mp[x]=++c;
add(i,i,0,mp[x]);
}
for(int i=1,op,l,r,x;i<=m;i++)
{
op=read(),l=read(),r=read();
if(op^2)
{
if(!mp[x=read()])
mp[x]=++c;
set<node>::iterator itr=split(r+1,i),itl=split(l,i);
for(set<node>::iterator it=itl,j;it!=itr;)
{
j=it;
it++;
del(j->l,j->r,i,j->w);
}
add(l,r,i,mp[x]);
}
else
query(l,r,i,ans[i]=0);
}
solve(0,m,1,k);
for(int i=1;i<=m;i++)
if(~ans[i])
write(ans[i]),puts("");
}