2320. [HZOI 2015]聰聰?shù)氖澜?/h1>

時(shí)間限制：6 s?? 內(nèi)存限制：512 MB

【題目描述】

?

背景：

聰聰?shù)男匀∠蛴袉栴}。

題目描述：

聰聰遇到了一個(gè)難題：

給出一個(gè)序列a1…an，完成以下操作：

1 ?x 詢問從x向左數(shù)第一個(gè)<ax的數(shù)；

2 ?x 詢問從x向左數(shù)第一個(gè)>ax的數(shù)；

3 ?x 詢問從x向右數(shù)第一個(gè)<ax的數(shù)；

4 ?x 詢問從x向右數(shù)第一個(gè)>ax的數(shù)；

5 ?x y 交換ax與ay；

6 ?x y w 給ax…ay加上w；

7 ?x y w 給ax…ay減去w。

聰聰急切的想知道答案，因?yàn)樗瓿扇蝿?wù)后就可以迎娶高富帥，出任CEO，走上人生巔峰，成為人生贏家！

請(qǐng)你幫幫他。

?

【輸入格式】

?

第一行 n，m。

第二行 a1…an。

第三行到m+2行為以上七個(gè)操作。

?

【輸出格式】

?

對(duì)于每個(gè)op>=1且op<=4輸出一行表示答案，無解輸出-1。

?

【樣例輸入】

?

5 5

8 2 0 0 9

1 2

5 1 3

7 1 3 1

4 2

1 1

?

【樣例輸出】

?

-1

7

-1

?

【提示】

?

10% ?n,m<=10000

40% ?n,m<=100000

100% ?n,m<=1000000

對(duì)于所有輸入的數(shù)保證在[0,10^9]范圍內(nèi)

?

　　學(xué)長(zhǎng)們出的題造的孽啊，貌似打法很多，我在這里只講一下線段樹解法。

　　首先先膜拜一下 ? ??神利·代目 ??stdafx.h，兩位學(xué)長(zhǎng)，我是在他們的引導(dǎo)下想出的O(log)時(shí)間復(fù)雜度內(nèi)完成前4個(gè)操作的。

　　因?yàn)檫@四個(gè)操作本質(zhì)一樣，因此我們就只講第一種操作。

　　請(qǐng)讀者自己先思考5~10分鐘，看看能否相出log復(fù)雜度的前四種操作打法，提醒一下，從根節(jié)點(diǎn)邊向下邊二分不靠譜。

　　開講了，首先，線段樹是一棵完全二叉樹，因此它滿足一個(gè)規(guī)律，兄弟節(jié)點(diǎn)的編號(hào)亦或1就是他自己，而它自己的編號(hào)/2就是他父親的編號(hào)，因此我們完全可以用這個(gè)性質(zhì)從下向上攀爬，再利用這個(gè)性質(zhì)從上向下攀爬。

1 #include<iostream> 2 #include<cstdlib> 3 #include<cstdio> 4 #include<cstring> 5 #include<queue> 6 #include<algorithm> 7 #include<cmath> 8 using namespace std; 9 long long n,m; 10 struct no{ 11 long long left,right; 12 long long mid,mn; 13 long long mx,lazy; 14 }node[4000004]; 15 long long a[1000005]; 16 long long dl[1000005]; 17 void build(long long left,long long right,long long x){ 18 node[x].left=left; 19 node[x].right=right; 20 if(left==right) 21 { 22 dl[left]=x; 23 node[x].mn=node[x].mx=a[left]; 24 return; 25 } 26 long long mid=(left+right)/2; 27 node[x].mid=mid; 28 build(left,mid,2*x); 29 build(mid+1,right,2*x+1); 30 node[x].mx=max(node[2*x].mx,node[2*x+1].mx); 31 node[x].mn=min(node[x*2].mn,node[2*x+1].mn); 32 } 33 void pushdown(long long x){ 34 if(node[x].lazy) 35 { 36 node[2*x].lazy+=node[x].lazy; 37 node[2*x+1].lazy+=node[x].lazy; 38 node[2*x].mx+=node[x].lazy; 39 node[2*x+1].mx+=node[x].lazy; 40 node[x*2].mn+=node[x].lazy; 41 node[2*x+1].mn+=node[x].lazy; 42 node[x].lazy=0; 43 } 44 } 45 long long get(long long left,long long right,long long x){ 46 if(node[x].left==node[x].right) 47 { 48 return node[x].mx; 49 } 50 pushdown(x); 51 long long mid=node[x].mid; 52 if(right<=node[x].mid) 53 return get(left,right,2*x); 54 else 55 return get(left,right,2*x+1); 56 } 57 void change(long long left,long long right,long long x,long long z){ 58 if(node[x].left==node[x].right) 59 { 60 node[x].mn=z; 61 node[x].mx=z; 62 return; 63 } 64 pushdown(x); 65 long long mid=node[x].mid; 66 if(right<=node[x].mid) 67 change(left,right,2*x,z); 68 else 69 change(left,right,2*x+1,z); 70 node[x].mx=max(node[2*x].mx,node[2*x+1].mx); 71 node[x].mn=min(node[2*x].mn,node[1+2*x].mn); 72 } 73 void add(long long left,long long right,long long x,long long z){ 74 if(node[x].left==left&&node[x].right==right) 75 { 76 node[x].mx+=z; 77 node[x].mn+=z; 78 node[x].lazy+=z; 79 return; 80 } 81 pushdown(x); 82 long long mid=node[x].mid; 83 if(right<=mid) 84 add(left,right,2*x,z); 85 else if(left>mid) 86 add(left,right,2*x+1,z); 87 else 88 add(left,mid,2*x,z),add(mid+1,right,2*x+1,z); 89 node[x].mx=max(node[2*x].mx,node[2*x+1].mx); 90 node[x].mn=min(node[x*2].mn,node[2*x+1].mn); 91 } 92 long long que_ls(long long x,long long z,long long buf){ 93 if(node[x].left==node[x].right) 94 return node[x].left; 95 if(node[2*x+1].mn+buf+node[x].lazy<z) 96 return que_ls(2*x+1,z,buf+node[x].lazy); 97 else 98 return que_ls(2*x,z,buf+node[x].lazy); 99 } 100 long long get_ls(long long x,long long z){ 101 if(x==1) 102 return -1; 103 if(!(x%2)) 104 return get_ls(x/2,z+node[x].lazy); 105 else 106 { 107 if(z+node[x].lazy>node[x^1].mn) 108 return que_ls(x^1,z+node[x].lazy,0); 109 else 110 return get_ls(x/2,z+node[x].lazy); 111 } 112 } 113 long long que_lb(long long x,long long z,long long buf){ 114 if(node[x].left==node[x].right) 115 return node[x].left; 116 if(node[2*x+1].mx+buf+node[x].lazy>z) 117 return que_lb(x*2+1,z,buf+node[x].lazy); 118 else 119 return que_lb(x*2,z,buf+node[x].lazy); 120 } 121 long long get_lb(long long x,long long z){ 122 if(x==1) 123 return -1; 124 if(!(x%2)) 125 return get_lb(x/2,z+node[x].lazy); 126 else 127 { 128 if(z+node[x].lazy<node[x^1].mx) 129 return que_lb(x^1,z+node[x].lazy,0); 130 else 131 return get_lb(x/2,z+node[x].lazy); 132 } 133 } 134 long long que_rs(long long x,long long z,long long buf){ 135 if(node[x].left==node[x].right) 136 return node[x].left; 137 if(node[2*x].mn+buf+node[x].lazy<z) 138 return que_rs(x*2,z,buf+node[x].lazy); 139 else 140 return que_rs(x*2+1,z,buf+node[x].lazy); 141 } 142 long long get_rs(long long x,long long z){ 143 if(x==1) 144 return -1; 145 if(x%2) 146 return get_rs(x/2,z+node[x].lazy); 147 else 148 { 149 if(z+node[x].lazy>node[x^1].mn) 150 return que_rs(x^1,z+node[x].lazy,0); 151 else 152 return get_rs(x/2,z+node[x].lazy); 153 } 154 } 155 long long que_rb(long long x,long long z,long long buf){ 156 if(node[x].left==node[x].right) 157 return node[x].left; 158 if(node[x*2].mx+buf+node[x].lazy>z) 159 return que_rb(x*2,z,buf+node[x].lazy); 160 else 161 return que_rb(x*2+1,z,buf+node[x].lazy); 162 } 163 long long get_rb(long long x,long long z){ 164 if(x==1) 165 return -1; 166 if(x%2) 167 return get_rb(x/2,z+node[x].lazy); 168 else 169 { 170 if(z+node[x].lazy<node[x^1].mx) 171 return que_rb(x^1,z+node[x].lazy,0); 172 else 173 return get_rb(x/2,z+node[x].lazy); 174 } 175 } 176 int main(){ 177 freopen("ccsworld.in","r",stdin); 178 freopen("ccsworld.out","w",stdout); 179 scanf("%lld%lld",&n,&m); 180 for(int i=1;i<=n;i++) 181 scanf("%lld",&a[i]); 182 build(1,n,1); 183 for(int i=1;i<=m;i++) 184 { 185 long long tt; 186 scanf("%lld",&tt); 187 if(tt==1) 188 { 189 long long x; 190 scanf("%lld",&x); 191 long long y=get_ls(dl[x],node[dl[x]].mx-node[dl[x]].lazy); 192 if(y!=-1) printf("%lld\n",get(y,y,1)); 193 else printf("%lld\n",y); 194 } 195 if(tt==2) 196 { 197 long long x; 198 scanf("%lld",&x); 199 long long y=get_lb(dl[x],node[dl[x]].mx-node[dl[x]].lazy); 200 if(y!=-1) printf("%lld\n",get(y,y,1)); 201 else printf("%lld\n",y); 202 } 203 if(tt==3) 204 { 205 long long x; 206 scanf("%lld",&x); 207 long long y=get_rs(dl[x],node[dl[x]].mx-node[dl[x]].lazy); 208 if(y!=-1) printf("%lld\n",get(y,y,1)); 209 else printf("%lld\n",y); 210 } 211 if(tt==4) 212 { 213 long long x; 214 scanf("%lld",&x); 215 long long y=get_rb(dl[x],node[dl[x]].mx-node[dl[x]].lazy); 216 if(y!=-1) printf("%lld\n",get(y,y,1)); 217 else printf("%lld\n",y); 218 } 219 if(tt==5) 220 { 221 long long x,y; 222 scanf("%lld%lld",&x,&y); 223 long long xx,yy; 224 xx=get(x,x,1); 225 yy=get(y,y,1); 226 change(x,x,1,yy); 227 change(y,y,1,xx); 228 } 229 if(tt==6) 230 { 231 long long x,y,z; 232 scanf("%lld%lld%lld",&x,&y,&z); 233 add(x,y,1,z); 234 } 235 if(tt==7) 236 { 237 long long x,y,z; 238 scanf("%lld%lld%lld",&x,&y,&z); 239 add(x,y,1,0-z); 240 } 241 } 242 //while(1); 243 return 0; 244 } 一份長(zhǎng)達(dá)5k的代碼，慎入

?

　　因此，我們大可開個(gè)數(shù)組存下每個(gè)葉節(jié)點(diǎn)的編號(hào)，便于查找，然后就從我們?cè)儐柕娜~節(jié)點(diǎn)向上查找，如果當(dāng)前位置為右子樹，那么就看一下他的兄弟的最小值是否比它小，如果不是，那么繼續(xù)向上爬，如果是，我們就從他的兄弟節(jié)點(diǎn)向下爬。如果當(dāng)前位置是左子樹，我們就得接著向上爬了，他的右子樹是不滿足條件的，因?yàn)楸绢}有區(qū)間操作，所以lazy數(shù)組就成了一個(gè)讓人頭痛的東西，讓我們來慢慢分析。

　　首先我向上爬時(shí)路徑上的lazy是影響的，因?yàn)槲覀兌际菑娜~節(jié)點(diǎn)向上爬，因此葉節(jié)點(diǎn)的數(shù)值是最晚更新的，因此向上爬的lazy是一定要加上的，那么有人可能回去問了，有可能之前還有區(qū)間操作只是沒下放呢，這就不必?fù)?dān)心了，因?yàn)槿绻麤]得到lazy，他的兄弟一定也沒得到，兩者抵消。

　　其次，向下爬的lazy也是會(huì)影響的，因?yàn)槲覀円氖亲羁拷黿的葉節(jié)點(diǎn)，因此我們應(yīng)采用先右后左的方法，如果右子樹的最小值比上面那步傳下來的參數(shù)小，就搜右子樹，左子樹就不必管了，而lazy也是需要一直跟著下放，原理見上。

　　我們最終傳回來的值并不是當(dāng)前節(jié)點(diǎn)的值，因?yàn)樯厦娴闹悼赡苓€沒傳下來，因此我們傳的應(yīng)當(dāng)是它的位置，再從根節(jié)點(diǎn)向下搞也就是單點(diǎn)查詢了。

　　至于其他三個(gè)操作，請(qǐng)讀者自己思考并實(shí)現(xiàn)。

　　打完代碼后提交，全WA，被QTY2001神犇提醒，沒開long long。交完就A了，沒啥坑點(diǎn)，主要是碼力，被教練員吐槽代碼能力弱的我都能在一小時(shí)之內(nèi)搞掉，這道題的難度也是沒誰了。這或許就是他只有3星的原因吧。

?

轉(zhuǎn)載于:https://www.cnblogs.com/liutianrui/p/7296123.html

《新程序員》：云原生和全面數(shù)字化實(shí)踐50位技術(shù)專家共同創(chuàng)作，文字、視頻、音頻交互閱讀

總結(jié)

以上是生活随笔為你收集整理的cogs 2320. [HZOI 2015]聪聪的世界题解的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。