[数据结构与算法]可持久化线段树11（简单剪枝）

CF840D Destiny

比价简单的主席树的题目，感觉分块也可以做。，没试过

根据题目意思，要求区间[l,r]中出现次数大于(r-l+1)/k的数中最小的数

一看和出现次数有关，基本就是主席树无疑了。

建树也比较简单，先离散化，后按一般主席树插入的方式建树即可。

查询也很简单，先看左子树，是否存在答案，如果存在答案，则不进入右子树，否则进入（这就是剪枝）

详见代码

#pragma GCC optimize(2)
#pragma GCC optimize(3,"Ofast","inline")
#include <bits/stdc++.h>
#define inf 0x7fffffff
//#define ll long long
//#define int long long
//#define double long double
#define re register int
#define void inline void
#define eps 1e-8
//#define mod 1e9+7
#define ls(p) p<<1
#define rs(p) p<<1|1
#define pi acos(-1.0)
#define pb push_back
#define P pair < int , int > 
#define mk make_pair
using namespace std;
const int mod=1e9+7;
const int M=1e8+5;
const int N=6e5+5;//?????????? 4e8
int a[N],b[N],rt[N];
int tot,n,q,m;
struct node
{
	int l,r,sum;
}e[N*40];
void insert(int &p,int pre,int l,int r,int d)
{
	e[++tot]=e[pre];
	p=tot;
	e[tot].sum++;
	if(l==r)  return;
	int mid=(l+r)>>1;
	if(d<=mid)  insert(e[p].l,e[pre].l,l,mid,d);
	else  insert(e[p].r,e[pre].r,mid+1,r,d);
}
int ask(int L,int R,int l,int r,int k)
{
	if(l==r)
	{
		if(e[R].sum-e[L].sum>k)  return l;
		else  return 1e9;
	}
	int mid=(l+r)>>1;
	int tl=e[e[R].l].sum-e[e[L].l].sum;
	int tr=e[e[R].r].sum-e[e[L].r].sum;
	int ans=1e9;
	if(tl>k)  ans=min(ans,ask(e[L].l,e[R].l,l,mid,k));
	if(tr>k&&ans==1e9)  ans=min(ans,ask(e[L].r,e[R].r,mid+1,r,k));
	return ans;
}
void solve()
{
	cin>>n>>q;
	for(re i=1;i<=n;i++)  scanf("%d",&a[i]),b[i]=a[i];
	sort(b+1,b+n+1);m=unique(b+1,b+n+1)-(b+1);
	for(re i=1;i<=n;i++)  insert(rt[i],rt[i-1],1,m,lower_bound(b+1,b+m+1,a[i])-b);
	while(q--)
	{
		int l,r,k;
		scanf("%d%d%d",&l,&r,&k);
		int ans=ask(rt[l-1],rt[r],1,m,(r-l+1)/k);
		if(ans==1e9)  ans=-1;
		else  ans=b[ans];
		printf("%d\n",ans);
	} 
}
signed main()
{
    int T=1;
//    cin>>T;
    for(int index=1;index<=T;index++)
    {
//    	printf("Case %d:\n",index);
        solve();
//        puts("");
    }
    return 0;
}
/*


5
10101
11
accd
acd
aaaaababa
ababa
aaaababa
ababa
avababa
ababa



 
*/