一个序列 \(a_i\), 每次询问 \((l,r,t)\), 表示询问 \([l,r]\) 内出现了大于 \(\frac{r-l+1}{t}\) 次的最大的数是什么.
\(n\le 10^5\)
感觉这题之前 CF 见过, 直接搬那题的做法...TLE...
事实证明这题正解比 CF 那题高到不知道哪里去了.
维护权值线段树, 建主席树, 表示一段前缀中每个树各自的出现次数. 线段树上维护和.
查找的时候, 如果当前权值区间总的出现次数大于 \(\frac{r-l+1}{t}\), 则继续走下去. 否则退出.
由于每一层至多有 \(t\) 个可以走下去的区间,\(\lg n\) 层, 所以一次询问时间复杂度 \(O(t\lg n)\)
这题告诉我们不要认为自己做了原题就万事大吉了.
- using namespace std;
- #include <cstdio>
- #include <cstring>
- #include <algorithm>
- #define N 100005
- int n,m;
- int a[N],re[N];
- int p[N];
- bool cmpp(int x,int y){return a[x]<a[y];}
- void inita(){
- for (int i=1;i<=n;++i)
- p[i]=i;
- sort(p+1,p+n+1,cmpp);
- for (int i=1,last=-1;i<=n;++i){
- if (a[p[i]]!=last)
- re[++m]=last=a[p[i]];
- a[p[i]]=m;
- }
- }
- struct Node{
- Node *l,*r;
- int sum;
- } d[N*20],*null,*rt[N];
- int cnt;
- Node *newnode(){return &(d[++cnt]={null,null,0});}
- void insert(Node *&now,Node *old,int l,int r,int x){
- now=newnode();
- *now=*old;
- now->sum++;
- if (l==r)
- return;
- int mid=l+r>>1;
- if (x<=mid) insert(now->l,old->l,l,mid,x);
- else insert(now->r,old->r,mid+1,r,x);
- }
- int en,st,T;
- int ans;
- void query(Node *R,Node *L,int l,int r){
- if (R->sum-L->sum<=(en-st+1)/T)
- return;
- if (l==r){
- ans=l;
- return;
- }
- int mid=l+r>>1;
- if (ans==-1) query(R->r,L->r,mid+1,r);
- if (ans==-1) query(R->l,L->l,l,mid);
- }
- int main(){
- freopen("in.txt","r",stdin);
- null=d;
- *null={null,null,0};
- int Q;
- scanf("%d%d",&n,&Q);
- for (int i=1;i<=n;++i)
- scanf("%d",&a[i]);
- inita();
- // for (int i=1;i<=n;++i)
- // printf("%d",a[i]);
- // printf("\n");
- rt[0]=null;
- for (int i=1;i<=n;++i){
- rt[i]=rt[i-1];
- insert(rt[i],rt[i-1],1,m,a[i]);
- }
- while (Q--){
- scanf("%d%d%d",&st,&en,&T);
- ans=-1;
- query(rt[en],rt[st-1],1,m);
- printf("%d\n",ans==-1?-1:re[ans]);
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-3685878.html