Destiny
题目大意
给定\(n\)个元素，\(m\)次询问。
每次给出三个参数\(l,r,k\)，询问区间\([l,r]\)内是否存在出现次数严格大于\(\frac{r-l+1}{k}\)的数。如果存在就输出最小的那个\(ans\)，否则输出\(-1\).
分析
我们看到要求区间[l,r]内存在的数字次数是否大于\(\frac{r-l+1}{k}\)，一定是直接想到要主席树了。
我说一下我的思路过程。
我先是想，我们能否通过主席树去维护出来[l,r]中这段中所有数字构成类似权值线段树那样维护他们数字出现次数的最大值。
然后发现是不太现实的，因为我们无法通过维护[1,l-1],[1,r]的信息去完成维护[l,r]的他们数字出现次数的最大值。
然后我就想，我们最能维护的东西其实是数量。然后我就想能不能考虑暴力。
然后就注意到，k的数据范围，\(2\leq k\leq5\)。
也就是说，我们如果直接在主席树上二分，条件就设置为该区间内的数字所有出现次数的和>\(\frac{r-l+1}{k}\)，我们也递归不了几次，顶天了是个\(logn+63\)，数量级也就是个\(O(logn)\)的。结束啦。
AC_code
#include<bits/stdc++.h>
#define ios ios::sync_with_stdio(false); cin.tie(0), cout.tie(0)
using namespace std;
using ll = long long;
const int N = 3e5 + 10;
struct Node
{
int l,r;
ll cnt;
}tr[N*24];
int root[N],idx;
int n,m;
int insert(int p,int l,int r,int x)
{
int q = ++idx;
tr[q]=tr[p];
if(l==r)
{
tr[q].cnt++;
return q;
}
int mid = l + r >> 1;
if(x<=mid) tr[q].l=insert(tr[q].l,l,mid,x);
else tr[q].r=insert(tr[q].r,mid+1,r,x);
tr[q].cnt=tr[tr[q].l].cnt+tr[tr[q].r].cnt;
return q;
}
int query(int q,int p,int l,int r,int k)
{
if(l==r) return l;
int mid = l + r >> 1;
ll ctl = tr[tr[q].l].cnt - tr[tr[p].l].cnt,ctr = tr[tr[q].r].cnt - tr[tr[p].r].cnt;
int res = -1;
if(ctl>k) res = query(tr[q].l,tr[p].l,l,mid,k);
if(res==-1&&ctr>k) return query(tr[q].r,tr[p].r,mid+1,r,k);
return res;
}
int main()
{
ios;cin>>n>>m;
for(int i=1;i<=n;i++)
{
int x;cin>>x;
root[i] = insert(root[i-1],1,n,x);
}
while(m--)
{
int l,r,k;cin>>l>>r>>k;
cout<<query(root[r],root[l-1],1,n,(r-l+1)/k)<<'\n';
}
return 0;
}