主席树||可持久化线段树||BZOJ 3524: [Poi2014]Couriers||BZOJ 2223: [Coci 2009]PATULJCI||Luogu P3567 [POI2014]KUR-Couriers

题目:[POI2014]KUR-Couriers

题解:

要求出现次数大于(R-L+1)/2的数,这样的数最多只有一个。我们对序列做主席树,每个节点记录出现的次数和(sum)。(这里忽略版本差值问题)对于一个节点,如果左儿子的sum小于等于(R-L+1)/2,则答案不可能在左儿子中;右儿子同理。然后对有可能的儿子递归寻找答案,如果左右儿子都不可能,则不存在答案。

代码:

BZOJ 3524:

 #include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
inline int rd(){
int x=,f=;char c=getchar();
while(c<''||c>''){if(c=='-')f=-; c=getchar();}
while(c>=''&&c<=''){x=x*+c-''; c=getchar();}
return f*x;
}
const int maxn=(5e5)+,maxm=maxn;
int N,M,L,R,root[maxn],num_treenode=,A;
struct Tree{
int l,r,sum,ls,rs;
}t[(maxn<<)+maxn*];
inline void Build(int x,int l,int r){
t[x].l=l;t[x].r=r;int mid=(l+r)>>;
if(l==r)return;
Build(t[x].ls=++num_treenode,l,mid);Build(t[x].rs=++num_treenode,mid+,r);
return;
}
inline void Update(int u,int x,int q){
int l=t[u].l,r=t[u].r,mid=(l+r)>>;
t[x].l=l;t[x].r=r;
if(l==r&&l==q){
t[x].sum=t[u].sum+;
return;
}
if(q<=mid){
t[x].rs=t[u].rs;
Update(t[u].ls,t[x].ls=++num_treenode,q);
}
else {
t[x].ls=t[u].ls;
Update(t[u].rs,t[x].rs=++num_treenode,q);
}
t[x].sum=t[t[x].ls].sum+t[t[x].rs].sum;
return;
}
inline int Query(int u,int x,int z){
int l=t[u].l,r=t[u].r;
if(l==r)return l;
if(t[t[x].ls].sum-t[t[u].ls].sum>z)return Query(t[u].ls,t[x].ls,z);
if(t[t[x].rs].sum-t[t[u].rs].sum>z)return Query(t[u].rs,t[x].rs,z);
return ;
}
int main(){
N=rd();M=rd();
Build(root[]=++num_treenode,,N);
for(int i=;i<=N;i++){
A=rd();
Update(root[i-],root[i]=++num_treenode,A);
}
while(M--){
L=rd();R=rd();
printf("%d\n",Query(root[L-],root[R],(R-L+)>>));
}
return ;
}

BZOJ 2223:

这道题的样例很坑,我整理了一下:


 #include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
inline int rd(){
int x=,f=;char c=getchar();
while(c<''||c>''){if(c=='-')f=-; c=getchar();}
while(c>=''&&c<=''){x=x*+c-''; c=getchar();}
return f*x;
}
const int maxn=(3e5)+,maxm=;
int N,M,L,R,root[maxn],num_treenode=,A,ans,Lim;
struct Tree{
int l,r,sum,ls,rs;
}t[(maxn<<)+maxn*];
inline void Build(int x,int l,int r){
t[x].l=l;t[x].r=r;int mid=(l+r)>>;
if(l==r)return;
Build(t[x].ls=++num_treenode,l,mid);Build(t[x].rs=++num_treenode,mid+,r);
return;
}
inline void Update(int u,int x,int q){
int l=t[u].l,r=t[u].r,mid=(l+r)>>;
t[x].l=l;t[x].r=r;
if(l==r&&l==q){
t[x].sum=t[u].sum+;
return;
}
if(q<=mid){
t[x].rs=t[u].rs;
Update(t[u].ls,t[x].ls=++num_treenode,q);
}
else {
t[x].ls=t[u].ls;
Update(t[u].rs,t[x].rs=++num_treenode,q);
}
t[x].sum=t[t[x].ls].sum+t[t[x].rs].sum;
return;
}
inline int Query(int u,int x,int z){
int l=t[u].l,r=t[u].r;
if(l==r)return l;
if(t[t[x].ls].sum-t[t[u].ls].sum>z)return Query(t[u].ls,t[x].ls,z);
if(t[t[x].rs].sum-t[t[u].rs].sum>z)return Query(t[u].rs,t[x].rs,z);
return ;
}
int main(){
N=rd();Lim=rd();
Build(root[]=++num_treenode,,Lim);
for(int i=;i<=N;i++){
A=rd();
Update(root[i-],root[i]=++num_treenode,A);
}
M=rd();
while(M--){
L=rd();R=rd();
if(L>R){
printf("no\n");
continue;
}
ans=Query(root[L-],root[R],(R-L+)>>);
if(ans==)printf("no\n");else printf("yes %d\n",ans);
}
return ;
}

By:AlenaNuna

上一篇:vue-单文件组件


下一篇:javascript双等号引起的类型转换