题目链接
求L,R内所有数字第一次出现的下标的中位数
区间第一次出现 即倒着的最后一次出现
所以我们倒着更新一个主席树
如果位置 I 的数字第一次出现 那么直接在第I颗树上的第I个位置加一即可
否则在加完1后 再在该数字的原位置减一
找BUG真的好难啊
✔
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int,int>pii;
typedef pair<LL,LL>pll;
const int maxn=2e5;
const int mod=1e9+7;
const int oo=1e9;
struct node
{
int l,r,sum;
}T[maxn*40+40];
int n,m,a[maxn+5],root[maxn+5],cnt,p[maxn+5],ans[maxn+5];
void update(int l,int r,int &x,int y,int pos,int val)
{
T[++cnt]=T[y];x=cnt;T[cnt].sum+=val;
if(l==r) return;
int mid=l+r>>1;
if(pos<=mid) update(l,mid,T[x].l,T[y].l,pos,val);
else update(mid+1,r,T[x].r,T[y].r,pos,val);
}
void del(int l,int r,int x,int pos)
{
T[x].sum--;
if(l==r) return;
int mid=l+r>>1;
if(pos<=mid) del(l,mid,T[x].l,pos);
else del(mid+1,r,T[x].r,pos);
}
int S(int l,int r,int x,int L,int R)
{
if(L<=l&&r<=R) return T[x].sum;
int mid=l+r>>1;
int ans=0;
if(L<=mid) ans=ans+S(l,mid,T[x].l,L,R);
if(R>mid) ans=ans+S(mid+1,r,T[x].r,L,R);
return ans;
}
int ask(int l,int r,int x,int k)
{
if(l==r) return l;
int sum=T[T[x].l].sum,mid=l+r>>1;
if(k<=sum) return ask(l,mid,T[x].l,k);
else return ask(mid+1,r,T[x].r,k-sum);
}
int main()
{
int _,cs=0;scanf("%d",&_);
while(_--){
memset(T,0,sizeof T);
memset(p,0,sizeof p);
memset(root,0,sizeof root);
cnt=0;
scanf("%d %d",&n,&m);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
for(int i=n;i>=1;i--){
update(1,n,root[i],root[i+1],i,1);
if(p[a[i]]){
update(1,n,root[i],root[i],p[a[i]],-1);
}
p[a[i]]=i;
}
int l,r;ans[0]=0;
for(int i=1;i<=m;i++){
scanf("%d %d",&l,&r);
l=(l+ans[i-1])%n+1;
r=(r+ans[i-1])%n+1;
if(l>r) swap(l,r);
int k=(S(1,n,root[l],l,r)+1)/2;
ans[i]=ask(1,n,root[l],k);
}
printf("Case #%d:",++cs);
for(int i=1;i<=m;i++){
printf(" %d",ans[i]);
}
printf("\n");
}
}
✖
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int,int>pii;
typedef pair<LL,LL>pll;
const int maxn=2e5;
const int mod=1e9+7;
const int oo=1e9;
struct node
{
int l,r,sum;
}T[maxn*40+40];
int n,m,a[maxn+5],root[maxn+5],cnt,p[maxn+5],ans[maxn+5];
void update(int l,int r,int &x,int y,int pos)
{
T[++cnt]=T[y];x=cnt;T[cnt].sum++;
if(l==r) return;
int mid=l+r>>1;
if(pos<=mid) update(l,mid,T[x].l,T[y].l,pos);
else update(mid+1,r,T[x].r,T[y].r,pos);
}
void del(int l,int r,int x,int pos)
{
T[x].sum--;
if(l==r) return;
int mid=l+r>>1;
if(pos<=mid) del(l,mid,T[x].l,pos);
else del(mid+1,r,T[x].r,pos);
}
int S(int l,int r,int x,int L,int R)
{
if(L<=l&&r<=R) return T[x].sum;
int mid=l+r>>1;
int ans=0;
if(L<=mid) ans=ans+S(l,mid,T[x].l,L,R);
if(R>mid) ans=ans+S(mid+1,r,T[x].r,L,R);
return ans;
}
int ask(int l,int r,int x,int k)
{
if(l==r) return l;
int sum=T[T[x].l].sum,mid=l+r>>1;
if(k<=sum) return ask(l,mid,T[x].l,k);
else return ask(mid+1,r,T[x].r,k-sum);
}
int main()
{
int _,cs=0;scanf("%d",&_);
while(_--){
memset(T,0,sizeof T);
memset(p,0,sizeof p);
memset(root,0,sizeof root);
cnt=0;
scanf("%d %d",&n,&m);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
for(int i=n;i>=1;i--){
update(1,n,root[i],root[i+1],i);
if(p[a[i]]){
del(1,n,root[i],p[a[i]]);
}
p[a[i]]=i;
}
int l,r;ans[0]=0;
for(int i=1;i<=m;i++){
scanf("%d %d",&l,&r);
l=(l+ans[i-1])%n+1;
r=(r+ans[i-1])%n+1;
if(l>r) swap(l,r);
int k=(S(1,n,root[l],l,r)+1)/2;
ans[i]=ask(1,n,root[l],k);
}
printf("Case #%d:",++cs);
for(int i=1;i<=m;i++){
printf(" %d",ans[i]);
}
printf("\n");
}
}