P1903 [国家集训队]数颜色 / 维护队列
  • 板块灌水区
  • 楼主EllehLucifenia
  • 当前回复2
  • 已保存回复2
  • 发布时间2020/8/26 22:00
  • 上次更新2023/11/6 19:14:01
查看原帖
P1903 [国家集训队]数颜色 / 维护队列
262083
EllehLucifenia楼主2020/8/26 22:00

蒟蒻刚学带修莫队,满怀期望的交上去,结果五颜六色。 希望有大佬能帮我一下 QAQ

#include<bits/stdc++.h>
using namespace std;
#define isdigit(ch) (ch>='0'&&ch<='9')
#define int long long
const int maxn=1e6+7;
#define il inline
il void read(int &x)
{
  x=0;char ch=getchar();
  while(!isdigit(ch)) ch=getchar();
  while(isdigit(ch)) {x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
}
struct miku{
  int l,r,id,t;
}q[maxn];
struct question{
  int pos,col; 
}c[maxn];
int n,m,a[maxn],cnt[maxn],now=0,l=1,r=0,t=0;
int bnum,size,belong[maxn],DFN,num,ans[maxn];
il bool cmp(miku a,miku b)
{
  return (belong[a.l]^belong[b.l])?belong[a.l]<belong[b.l]:((belong[a.r]^belong[b.r])?belong[a.r]<belong[b.r]:a.t<b.t);
}
il void add(int pos)
{
  if(!cnt[a[pos]]) ++now;
  ++cnt[a[pos]];
}
il void del(int pos)
{
  --cnt[a[pos]];
  if(!cnt[a[pos]]) --now;
}
il void change(int l,int r,int x)
{
  int pos=c[x].pos,Col=c[x].col;
  if(pos>=l&&pos<=r) 
  {
  	cnt[a[pos]]--;
  	if(!cnt[a[pos]]) now--;
  	if(!cnt[Col]) now++;
  	cnt[Col]++;
  }
  swap(a[pos],Col);
}
signed main()
{
//	freopen("6.in","r",stdin);
//	freopen("IA.out","w",stdout);
  read(n),read(m);
  size=pow(n,5.0/12);
  bnum=ceil((double)n/size);
  for(int i=1;i<=bnum;i++)
  	for(int j=(i-1)*size+1;j<=size*i;j++)
  		belong[j]=i;
  for(int i=1;i<=n;i++) read(a[i]);
  for(int i=1;i<=m;i++)
  {
  	char opt[5];
  	scanf("%s",opt);;
  	if(opt[0]=='Q') 
  	{
  		++num;
  		read(q[num].l),read(q[num].r);
  		q[num].id=num,q[num].t=DFN;
  	}
  	if(opt[0]=='R')
  	{
  		++DFN;
  		read(c[DFN].pos),read(c[DFN].col);
  	}
  }
  sort(q+1,q+1+num,cmp);
  for(int i=1;i<=num;i++)
  {
  	int ql=q[i].l,qr=q[i].r,pos=q[i].id,qt=q[i].t;
  	while(l<ql) del(l++);
  	while(l>ql) add(--l);
  	while(r<qr) add(++r);
  	while(r>qr) del(r--);
  	while(t<qt) change(ql,qr,++t);
  	while(t>qt) change(ql,qr,t--);
  	ans[pos]=now;
  }
  for(int i=1;i<=num;i++) printf("%lld\n",ans[i]);
  return 0;
}
2020/8/26 22:00
加载中...