首页 > 代码库 > [POI2014]Couriers

[POI2014]Couriers

2024-10-26 19:59:02   208人阅读

OJ题号：BZOJ3524、BZOJ2223、洛谷3567

思路：

维护一颗可持久化权值线段树，记录每次加入数字时，不同数字出现的个数。
对于每一个询问$[l,r]$，同时查询以$r$和$l-1$为根的线段树，每次比较两个节点左右字子树的权值和，如果大于$[l,r]$区间的一半就说明这一子区间可能有答案，递归查询即可。

 1 #include<cstdio> 2 #include<cctype> 3 #include<cstring> 4 inline int getint() { 5     char ch; 6     while(!isdigit(ch=getchar())); 7     int x=ch^‘0‘; 8     while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^‘0‘); 9     return x;10 }11 const int N=500001,SZ=10000001;12 class FotileTree {13     private:14         int val[SZ],sz,left[SZ],right[SZ];15         int newnode() {16             return sz++;17         }18     public:19         FotileTree() {20             sz=0;21             memset(val,0,sizeof val);22         }23         int root[N];24         int build(const int b,const int e) {25             int new_p=newnode();26             if(b==e) return new_p;27             int mid=(b+e)>>1;28             left[new_p]=build(b,mid);29             right[new_p]=build(mid+1,e);30             return new_p;31         }32         int modify(const int p,const int b,const int e,const int x) {33             int new_p=newnode();34             val[new_p]=val[p]+1;35             if(b==e) return new_p;36             int mid=(b+e)>>1;37             if(x<=mid) left[new_p]=modify(left[p],b,mid,x),right[new_p]=right[p];38             if(x>mid) right[new_p]=modify(right[p],mid+1,e,x),left[new_p]=left[p];39             return new_p;40         }41         int query(const int p1,const int p2,const int b,const int e,const int k) {42             if(b==e) return b;43             int mid=(b+e)>>1;44             if(val[left[p2]]-val[left[p1]]>k) return query(left[p1],left[p2],b,mid,k);45             if(val[right[p2]]-val[right[p1]]>k) return query(right[p1],right[p2],mid+1,e,k);46             return 0;47         }48 };49 FotileTree t;50 int main() {51     int n=getint(),m=getint();52     t.root[0]=t.build(1,n);53     for(int i=1;i<=n;i++) t.root[i]=t.modify(t.root[i-1],1,n,getint());54     while(m--) {55         int l=getint(),r=getint();56         printf("%d\n",t.query(t.root[l-1],t.root[r],1,n,(r-l+1)>>1));57     }58     return 0;59 }

 

[POI2014]Couriers


联系
我们