2019 Multi-University Training Contest 2 1011主席树

「爱情、让人受尽委屈。」 2021-11-22 13:14 201阅读 0赞

Problem Description

N sticks are arranged in a row, and their lengths are a1,a2,...,aN.  
  
There are Q querys. For i-th of them, you can only use sticks between li-th to ri-th. Please output the maximum circumference of all the triangles that you can make with these sticks, or print −1 denoting no triangles you can make.

Input

There are multiple test cases.  
  
Each case starts with a line containing two positive integers N,Q(N,Q≤105).  
  
The second line contains N integers, the i-th integer ai(1≤ai≤109) of them showing the length of the i-th stick.  
  
Then follow Q lines. i-th of them contains two integers li,ri(1≤li≤ri≤N), meaning that you can only use sticks between li-th to ri-th.  
  
It is guaranteed that the sum of Ns and the sum of Qs in all test cases are both no larger than 4×105.

Output

For each test case, output Q lines, each containing an integer denoting the maximum circumference.

题意：给出一个数列，询问任意区间，区间内所组成的最大的三角形周长是多少？

首先要明白斐波那契的一个性质，刚刚好不能够组成三角形，然后根据这个性质，1e9的范围内，如果一直不能构成三角形，最大只有47个数(47层)。这样我们从每个区间取出最大的47个数，然后来判断这47个数满足题意的三角形周长就可以了。

很明显主席树查询第k大模板。

//#include<iostream>
    //#include<cstdio> 
    //#include<algorithm>
    #include<bits/stdc++.h>
    using namespace std;
    const int M=1e5+50; 
    int n,q,d[M],b[M],root[M],cnt;
    struct Node{int l,r,sum;}t[40*M];
    void build(int &rot,int l,int r){
    	rot=++cnt;
    	t[rot].sum=0;
    	if(l==r)return ;
    	int mid=(l+r)>>1;
    	build(t[rot].l,l,mid);
    	build(t[rot].r,mid+1,r);
    } 
    void update(int &rot,int l,int r,int last ,int v){
    	rot=++cnt;
    	t[rot].l=t[last].l;
    	t[rot].r=t[last].r;
    	t[rot].sum=t[last].sum+1;
    	if(l==r)return ;
    	int mid=(l+r)>>1;
    	if(v<=mid)update(t[rot].l,l,mid,t[last].l,v);
    	if(mid<v)update(t[rot].r,mid+1,r,t[last].r,v);
    }
    bool judge(int x,int y,int z){
    	char xx[3];
    	xx[0]=x;
    	xx[1]=y;
    	xx[2]=z;
    	sort(xx,xx+3);
    	if(xx[0]+xx[1]<=xx[2])return false;
    	return true;
    }
    int ask(int pre,int now,int l,int r,int k){
    	if(l==r)return l;
    	int mid=(l+r)>>1,num=t[t[now].r].sum-t[t[pre].r].sum;
    	if(k<=num)return ask(t[pre].r,t[now].r,mid+1,r,k);
    	return ask(t[pre].l,t[now].l,l,mid,k-num);
    }
    int main(){
    	while(scanf("%d%d",&n,&q)!=EOF){ 
    		cnt=0;
    		
    		for(int i=1;i<=n;i++){
    			scanf("%d",d+i);
    			b[i]=d[i];
    		}
    		sort(b+1,b+n+1);		
    		int sz=unique(b+1,b+n+1)-(b+1);	
    		for(int i=1;i<=n;i++)d[i]=lower_bound(b+1,b+sz+1,d[i])-b;
    		build(root[0],1,sz); 
    		for(int i=1;i<=n;i++)update(root[i],1,sz,root[i-1],d[i]); //通过上个树，来更新这个树 
    		long long  res[55]; 
    		for(int x,y,k,mx,f,i=1;i<=q;i++){
    			scanf("%d%d",&x,&y);
    			mx=min(50,y-x+1);
    			if(mx<3){
    				printf("-1\n");
    				continue;
    			}
    			for(int j=1;j<=mx;j++) res[j] = b[ask(root[x-1],root[y],1,sz,j)]; //找到第k大的数字 
    			f=0;
    			for(int j=3;j<=mx;j++){
    				if(res[j]+res[j-1]>res[j-2]){
    					f=1;
    					printf("%lld\n",res[j]+res[j-1]+res[j-2]);
    					break;
    				}
    			}
    			if(!f)printf("-1\n");
    		}
    	}			
    	return 0;
    }

跑了2.6秒 ，这一题卡常数(差点想用莫队干这题，但是想想算了，莫队T飞).