@OceanEye7年前
04/12
23:33
很强的题目= =超级烦
想来想去想不懂怎么写
一个很朴素的想法就是排序然后一个一个加进去
假设当前已经满足可以取[0,P]之间的取值
新进来一个数q
如果q在[0,P+1]之间的话就可以拓展 P -> P+q
否则停止拓展，因为显然后面那一堆都不满足要求
然后我就不会了= =跑去翻了翻题解 [传送门]
发现可以连着处理一段的sum，时间复杂度大致是单次log方的。
真神奇
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 |
#include <cstdio> #include <algorithm> #define ll long long #define p(x) ('0'<=x&&x<='9') char cc; template <class T> void read( T &x ) { cc=getchar(); x=0; while(!p(cc)) cc=getchar(); while(p(cc)) { x=x*10+cc-48; cc=getchar(); } } using namespace std; #define N 100010 #define inf 1000000000 namespace Segent_Tree { struct node { int lc,rc; ll sum; }pool[N<<6]; #define Lc pool[x].lc #define Rc pool[x].rc #define LC pool[x2].lc #define RC pool[x2].rc #define SUM pool[x].sum #define VAL pool[x].val #define DEC pool[x].sum-pool[x2].sum int pcnt,rt[N],now; void init() { // pool[rt[0]].l=1; pool[rt[0]].r=N; pcnt=rt[0]=1; } void PushUP(int x) { SUM=pool[Lc].sum+pool[Rc].sum; } void insert(int &x,const ll & val,int l,int r) { pool[++pcnt]=pool[x]; x=pcnt; if(l==r) { pool[x].sum+=val; return; } int mid=(l+r)>>1; if(mid>=val) insert(pool[x].lc,val,l,mid); else insert(pool[x].rc,val,mid+1,r); PushUP(x); } void add(ll x) { rt[now+1]=rt[now]; now++; insert(rt[now],x,1,inf); } ll query(int x2,int x,int l,int r,int L,int R) { if(L<=l&&r<=R) { return DEC; } int mid=(l+r) >>1; ll ret=0; if(mid>=L) ret+=query(LC,Lc,l,mid,L,R); if(mid+1<=R) ret+=query(RC,Rc,mid+1,r,L,R); return ret; } ll solve(int l,int r) { ll mx=1,p=query(rt[l-1],rt[r],1,inf,1,1); while(p>=mx) { mx=p+1; p=query(rt[l-1],rt[r],1,inf,1,mx); } return mx; } } int n,_,__; int main() { Segent_Tree::init(); read(n); while(n--) { read(_); Segent_Tree::add(_); } read(n); while(n--) { read(_); read(__); if(_>__) swap(_,__); printf("%lld\n",Segent_Tree::solve(_,__)); } return 0; } |