首先环可以变成链来处理，对于l>r的情况就是修改区间[1,r],[l,mx]
然后不难想到整体二分，二分答案k,然后算1~k场流星雨对国家的贡献然后判定将国家划分变成子问题解决，没什么难的终于不是tle，poi良心了一把
1 type way=record 2 po,next:longint; 3 end; 4 que=record 5 p,n:longint; 6 end; 7 an=record 8 l,r,v:longint; 9 end; 10 var a:array[0..300010] of an; 11 qq,q:array[0..300010] of que; 12 e:array[0..300010] of way; 13 c:array[0..300010] of int64; 14 p,ans,h:array[0..300010] of longint; 15 v:array[0..300010] of boolean; 16 tot,t,j,n,m,x,i:longint; 17 s:int64; 18 19 function lowbit(x:longint):longint; 20 begin 21 exit(x and (-x)); 22 end; 23 24 procedure add(x,y:longint); 25 begin 26 e[i].po:=i; 27 e[i].next:=p[x]; 28 p[x]:=i; 29 end; 30 31 procedure ins(x:longint;w:int64); 32 begin 33 while x<=n do 34 begin 35 if not v[x] then //清理标记 36 begin 37 inc(tot); 38 h[tot]:=x; 39 v[x]:=true; 40 end; 41 c[x]:=c[x]+w; 42 x:=x+lowbit(x); 43 end; 44 end; 45 46 function ask(x:longint):int64; 47 begin 48 ask:=0; 49 while x>0 do 50 begin 51 ask:=ask+c[x]; 52 x:=x-lowbit(x); 53 end; 54 end; 55 56 procedure work(f,t,l,r:longint); 57 var mid,l1,l2:longint; 58 begin 59 if f>t then exit; 60 if l>r then exit; 61 mid:=(l+r) shr 1; 62 tot:=0; 63 for i:=l to mid do 64 if a[i].l<=a[i].r then 65 begin 66 ins(a[i].l,a[i].v); 67 ins(a[i].r+1,-a[i].v); 68 end 69 else begin 70 ins(1,a[i].v); 71 ins(a[i].r+1,-a[i].v); 72 ins(a[i].l,a[i].v); 73 end; 74 75 l1:=f; 76 l2:=t; 77 for i:=f to t do 78 begin 79 j:=p[q[i].p]; 80 s:=0; 81 while j<>0 do 82 begin 83 s:=s+ask(e[j].po); 84 if s>=q[i].n then 85 begin 86 qq[l1]:=q[i]; 87 inc(l1); 88 ans[q[i].p]:=mid; 89 break; 90 end; 91 j:=e[j].next; 92 end; 93 if s