标签：cnt int sum KUR POI2014 mid tot ans Couriers
- 可持久化线段树
- 维护由任意一段区间得到的权值线段树
- 线段树的深度：\(ceil(log_{2}(n))+1\)
- 由于询问的特殊性，我们可以直接在线段树上二分，而不需要另写查询函数，从而节省掉1个log的复杂度
点击查看代码
#include <bits/stdc++.h>
using namespace std;
int tot,root[500005];
int read1()
{
char cc=getchar();
while(!(cc>=48&&cc<=57))
{
if(cc=='-')
{
break;
}
cc=getchar();
}
bool f=false;
int s=0;
if(cc=='-')
{
f=true;
}
else
{
s=cc-48;
}
while(1)
{
cc=getchar();
if(cc>=48&&cc<=57)
{
s=s*10+cc-48;
}
else
{
break;
}
}
if(f==true)
{
s=-s;
}
return s;
}
struct t1
{
int l,r,cnt;
}t[11000005];
int build(int l,int r)
{
if(l==r)
{
tot++;
t[tot].cnt=0;
return tot;
}
int mid=(l+r)>>1;
tot++;
int p=tot;
t[p].l=build(l,mid);
t[p].r=build(mid+1,r);
t[p].cnt=0;
return tot;
}
int insert(int c,int q,int l,int r)
{
tot++;
int p=tot;
if(c==l&&l==r)
{
t[p].cnt=t[q].cnt+1;
return p;
}
int mid=(l+r)>>1;
if(c<=mid)
{
t[p].l=insert(c,t[q].l,l,mid);
t[p].r=t[q].r;
}
else
{
t[p].r=insert(c,t[q].r,mid+1,r);
t[p].l=t[q].l;
}
t[p].cnt=t[t[p].l].cnt+t[t[p].r].cnt;
return p;
}
/*
int ask(int l,int r,int p,int u,int v)
{
if(l<=u&&v<=r)
{
return t[p].cnt;
}
int mid=(u+v)>>1;
int ans=0;
if(l<=mid)
{
ans=ans+ask(l,r,t[p].l,u,mid);
}
if(r>mid)
{
ans=ans+ask(l,r,t[p].r,mid+1,v);
}
return ans;
}
*/
int main()
{
// freopen("P3567_53.in","r",stdin);
// cout<<500000*20*4*3/1024/1024<<endl;
int n,m;
cin>>n>>m;
root[0]=build(1,n);
for(int i=1;i<=n;i++)
{
int a=read1();
root[i]=insert(a,root[i-1],1,n);
}
for(int i=1;i<=m;i++)
{
int u,v,len;
u=read1();
v=read1();
len=v-u+1;
int l=1,r=n,sum=len;
u=root[u-1];v=root[v];
bool f=true;
while(l<r)
{
int mid=(l+r)>>1;
//int cnt=ask(l,mid,root[v],1,n)-ask(l,mid,root[u-1],1,n);
int cnt=t[t[v].l].cnt-t[t[u].l].cnt;
if(2*cnt>len)
{
r=mid;
sum=cnt;
u=t[u].l;
v=t[v].l;
}
else if(2*(sum-cnt)>len)
{
l=mid+1;
sum=sum-cnt;
u=t[u].r;
v=t[v].r;
}
else
{
f=false;
break;
}
}
if(f==true)
{
printf("%d\n",l);
}
else
{
printf("0\n");
}
}
return 0;
}
标签：cnt,
int,
sum,
KUR,
POI2014,
mid,
tot,
ans,
Couriers
From： https://www.cnblogs.com/watersail/p/17982896