ps如何做psd模板下载网站,蚌埠网络推广公司,网站颜色搭配技巧,免费企业名录搜索软件首先环可以变成链来处理#xff0c;对于lr的情况就是修改区间[1,r],[l,mx]然后不难想到整体二分#xff0c;二分答案k,然后算1~k场流星雨对国家的贡献然后判定将国家划分变成子问题解决#xff0c;没什么难的终于不是tle#xff0c;poi良心了一把 1 type wayrecord2 …首先环可以变成链来处理对于lr的情况就是修改区间[1,r],[l,mx]然后不难想到整体二分二分答案k,然后算1~k场流星雨对国家的贡献然后判定将国家划分变成子问题解决没什么难的终于不是tlepoi良心了一把 1 type wayrecord2 po,next:longint;3 end;4 querecord5 p,n:longint;6 end;7 anrecord8 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 begin21 exit(x and (-x));22 end;23 24 procedure add(x,y:longint);25 begin26 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 begin33 while xn do34 begin35 if not v[x] then //清理标记36 begin37 inc(tot);38 h[tot]:x;39 v[x]:true;40 end;41 c[x]:c[x]w;42 x:xlowbit(x);43 end;44 end;45 46 function ask(x:longint):int64;47 begin48 ask:0;49 while x0 do50 begin51 ask:askc[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 begin59 if ft then exit;60 if lr then exit;61 mid:(lr) shr 1;62 tot:0;63 for i:l to mid do64 if a[i].la[i].r then65 begin66 ins(a[i].l,a[i].v);67 ins(a[i].r1,-a[i].v);68 end69 else begin70 ins(1,a[i].v);71 ins(a[i].r1,-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 do78 begin79 j:p[q[i].p];80 s:0;81 while j0 do82 begin83 s:sask(e[j].po);84 if sq[i].n then85 begin86 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 sq[i].n then94 begin95 q[i].n:q[i].n-s; //对于还不够的国家直接把这部分贡献减去即可下次直接处理mid之后的流星雨的贡献96 qq[l2]:q[i];97 dec(l2);98 end;99 end;
100 for i:1 to tot do
101 begin
102 c[h[i]]:0;
103 v[h[i]]:false;
104 end;
105 for i:f to t do
106 q[i]:qq[i];
107 work(f,l1-1,l,mid-1);
108 work(l21,t,mid1,r);
109 end;
110
111 begin
112 readln(m,n);
113 for i:1 to n do
114 begin
115 read(x);
116 add(x,i);
117 end;
118 for i:1 to m do
119 begin
120 read(q[i].n);
121 q[i].p:i;
122 end;
123 readln(t);
124 for i:1 to t do
125 readln(a[i].l,a[i].r,a[i].v);
126 work(1,m,1,t);
127 for i:1 to m do
128 if ans[i]0 then writeln(NIE)
129 else writeln(ans[i]);
130 end. View Code 转载于:https://www.cnblogs.com/phile/p/4472945.html
