【HDOJ6601】Keen On Everything But Triangle（主席树）

题意：给定一个长为n的序列，有q次询问，每次询问[l,r]这段区间内挑三个数，能组成的三角形的最大周长，无解输出-1

n,q<=1e5，a[i]<=1e9

思路：题解写法和我的不太一样

先说题解做法，显然最坏情况下是斐波那契数列的形式，大概是log2(1e9)项就没有-1了，所以维护一个可以取某一段中前50大的数字的数据结构，取出来之后sort看相邻3个取max即可

我的做法是用主席树把区间权值抠出来，树上二分权值，如果当前结点的右儿子的size>=3就必定是最优解，否则把右儿子中的所有数取出来再递归左儿子，最后同sort处理

原理应该差不多

  1 #include<bits/stdc++.h>
  2 using namespace std;
  3 typedef long long ll;
  4 typedef unsigned int uint;
  5 typedef unsigned long long ull;
  6 typedef pair<int,int> PII;
  7 typedef pair<ll,ll> Pll;
  8 typedef vector<int> VI;
  9 #define N  110000
 10 #define M  1100000
 11 #define fi first
 12 #define se second
 13 #define MP make_pair
 14 #define pi acos(-1)
 15 #define mem(a,b) memset(a,b,sizeof(a))
 16 #define rep(i,a,b) for(int i=(int)a;i<=(int)b;i++)
 17 #define per(i,a,b) for(int i=(int)a;i>=(int)b;i--)
 18 #define lowbit(x) x&(-x)
 19 #define Rand (rand()*(1<<16)+rand())
 20 #define id(x) ((x)<=B?(x):m-n/(x)+1)
 21 #define ls p<<1
 22 #define rs p<<1|1
 23 
 24 const ll MOD=998244353,inv2=(MOD+1)/2;
 25       double eps=1e-6;
 26       ll INF=1e14;
 27 
 28 struct arr
 29 {
 30     int l,r,s;
 31 }t[N*50];
 32 
 33 int c[N],root[N],flag,m,cnt;
 34 ll ans;
 35 
 36 int read()
 37 {
 38    int v=0,f=1;
 39    char c=getchar();
 40    while(c<48||57<c) {if(c=='-') f=-1; c=getchar();}
 41    while(48<=c&&c<=57) v=(v<<3)+v+v+c-48,c=getchar();
 42    return v*f;
 43 }
 44 
 45 void update(int l,int r,int x,int &p)
 46 {
 47     t[++cnt]=t[p];
 48     p=cnt;
 49     t[p].s++;
 50     if(l==r) return;
 51     int mid=(l+r)>>1;
 52     if(x<=mid) update(l,mid,x,t[p].l);
 53      else update(mid+1,r,x,t[p].r);
 54 }
 55 
 56 int find(int l,int r,int x,int p1,int p2)
 57 {
 58     //printf("find l=%d r=%d
",l,r);
 59     int tmp=t[p2].s-t[p1].s;
 60     if(x<=0) return 0;
 61     if(!tmp) return 0;
 62     if(l==r)
 63     {
 64         rep(i,1,min(3,tmp)) c[++m]=l;
 65         return min(3,tmp);
 66     }
 67     int mid=(l+r)>>1;
 68     x-=find(mid+1,r,x,t[p1].r,t[p2].r);
 69     find(l,mid,x,t[p1].l,t[p2].l);
 70     return tmp;
 71 }
 72 
 73 void query(int l,int r,int p1,int p2)
 74 {
 75     if(l>r) return;
 76     if(l==r)
 77     {
 78         rep(i,1,min(3,t[p2].s-t[p1].s)) c[++m]=l;
 79         return;
 80     }
 81     int mid=(l+r)>>1;
 82     int tmp=t[t[p2].r].s-t[t[p1].r].s;
 83     if(tmp>=3)
 84     {
 85         find(mid+1,r,3,t[p1].r,t[p2].r);
 86         return;
 87     }
 88      else
 89      {
 90          if(tmp) find(mid+1,r,tmp,t[p1].r,t[p2].r);
 91          query(l,mid,t[p1].l,t[p2].l);
 92      }
 93 }
 94 
 95 
 96 int main()
 97 {
 98     int n,q;
 99     while(scanf("%d%d",&n,&q)!=EOF)
100     {
101         rep(i,1,cnt) t[i].l=t[i].r=t[i].s=0;
102         cnt=1; root[0]=1;
103         rep(i,1,n)
104         {
105             int x=read();
106             root[i]=root[i-1];
107             update(1,1e9,x,root[i]);
108         }
109         while(q--)
110         {
111             int x=read(),y=read();
112             ans=0;
113             m=0;
114             flag=0;
115             query(1,1e9,root[x-1],root[y]);
116             //printf("flag=%d
",flag);
117             sort(c+1,c+m+1);
118             //printf("m=%d
",m);
119             //rep(i,1,m) printf("%d
",c[i]);
120             rep(i,2,m-1)
121              if(c[i]+c[i-1]>c[i+1]) ans=max(ans,0ll+c[i-1]+c[i]+c[i+1]);
122 
123              if(ans==0) printf("-1
");
124               else printf("%I64d
",ans);
125              rep(i,1,m) c[i]=0;
126         }
127 
128 
129     }
130     return 0;
131 }