MY（一名蒟蒻）
2021-05-03 20:25:23
CF840D Destiny
P3567 [POI2014]KUR-Couriers的加强版。
看到这题我第一反应是莫队来着。
由于这题非常模板所以我来介绍一下这玩意是啥。
以下摘自本人的题解 P6166 【[IOI2012]scrivener】
主席树，又名函数式线段树。由于发明人黄嘉泰的名字缩写和某位中国共产党领导人是一样的，故名主席树。
实现可持久化使用复制节点的方式，由于一次修改最多修改
又叫可持久化线段树，顾名思义可持久。
这个东西可以在一个数列中挖出一段来做
本题依靠权值线段树。
就是节点维护的不是区间的信息，而是值域上的信息。
每一个节点对应的是值域上的一段区间。
所以离散化是值域线段树经典操作。
边插入边建树，每次对树的形态产生更改时复制节点。
这里不能再使用线段树访问左右儿子的方式，要记录下每个节点的左右儿子。
插入时从内存池中取一块内存给复制的节点，每一次插入建立在上一个版本上。
先来看弱化版的询问咋搞。
因为这题权值线段树每个数字的贡献是所在区间的个数加一，所以如果我们用
那么如果左子区间有数字出现次数超过一半就递归查左子，否则右子。
注意这里的左子区间是值域线段树上的左子区间。
递归的时候要把区间的左右端点一起传下去，注意这里的区间指的是数列上的区间。
可能很绕啊，放一下代码吧。
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
const int N=5e5+10;
int n,m,a,cnt,rt[N];
struct node {int l,r,sum;} hjt[N << 5];//32倍空间
inline int clone(int o) {hjt[++cnt]=hjt[o]; return cnt;}//复制节点
int build(int o,int l,int r,int p)//边插入边建树
{
o=clone(o); hjt[o].sum++;//权值线段树对应区间个数++
if(l == r) return o;
int mid=(l+r) >> 1;
if(p <= mid) hjt[o].l=build(hjt[o].l,l,mid,p);
else hjt[o].r=build(hjt[o].r,mid+1,r,p);
return o;
}
int query(int l,int r,int L,int R,int size)
{
if(l == r) return l;
int mid=(l+r) >> 1;//有点像差分
if((hjt[hjt[R].l].sum-hjt[hjt[L].l].sum)<<1 > size) return query(l,mid,hjt[L].l,hjt[R].l,size);
if((hjt[hjt[R].r].sum-hjt[hjt[L].r].sum)<<1 > size) return query(mid+1,r,hjt[L].r,hjt[R].r,size);
return 0;
}
int main()
{
// freopen("work.in","r",stdin); freopen("work.out","w",stdout);
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) {scanf("%d",&a); rt[i]=build(rt[i-1],1,n,a);}
int l,r;
while(m--)
{
scanf("%d%d",&l,&r);
printf("%d\n",query(1,n,rt[l-1],rt[r],r-l+1));
}
// fclose(stdin); fclose(stdout);
return 0;
}我根据这题的描述把
int query(int l,int r,int L,int R,int size)
{
if(l == r) return l;
int mid=(l+r) >> 1;
if(hjt[hjt[R].l].sum-hjt[hjt[L].l].sum > size) return query(l,mid,hjt[L].l,hjt[R].l,size);
if(hjt[hjt[R].r].sum-hjt[hjt[L].r].sum > size) return query(mid+1,r,hjt[L].r,hjt[R].r,size);
return -1;
}但是这个玩意WA了#6。
因为如果当前你判断左边的区间满足条件，但是答案不一定在左边。左边只是总次数满足条件，但是答案也可能在右边。
接下来直接放代码。不再注释。
/*
主席树 P3567加强版
边插入边建树
经典操作边递归边减
与弱化版的区别在于没有一个性质：具有唯一解
也就是说，当前你判断左边的区间满足条件，但是答案不一定在左边
所以如果左边无解，要考虑右边是否有解
*/
#include <cstdio>
#include <iostream>
using namespace std;
const int N=3e5+10;
int n,m,k,cnt,rt[N];
struct node {int l,r,sum;} hjt[N << 5];
inline int clone(int o) {hjt[++cnt]=hjt[o]; return cnt;}
int build(int o,int l,int r,int p)
{
o=clone(o); hjt[o].sum++;
if(l == r) return o;
int mid=(l+r) >> 1;
if(p <= mid) hjt[o].l=build(hjt[o].l,l,mid,p);
else hjt[o].r=build(hjt[o].r,mid+1,r,p);
return o;
}
int query(int l,int r,int L,int R,int size)
{
if(l == r) return l;
int mid=(l+r) >> 1,res;
if((hjt[hjt[R].l].sum-hjt[hjt[L].l].sum)*k > size)
{
res=query(l,mid,hjt[L].l,hjt[R].l,size);
if(~res) return res;
}
if((hjt[hjt[R].r].sum-hjt[hjt[L].r].sum)*k > size) return query(mid+1,r,hjt[L].r,hjt[R].r,size);
return -1;
}
int main()
{
// freopen("work.in","r",stdin); freopen("work.out","w",stdout);
scanf("%d%d",&n,&m);
for(int i=1,x;i<=n;i++) {scanf("%d",&x); rt[i]=build(rt[i-1],1,n,x);}
int l,r;
while(m--)
{
scanf("%d%d%d",&l,&r,&k);
printf("%d\n",query(1,n,rt[l-1],rt[r],r-l+1));
}
// fclose(stdin); fclose(stdout);
return 0;
}希望对您学OI有帮助！