題目鏈接：點(diǎn)擊查看
題目大意：初始時(shí)給出 n 個(gè)數(shù)字組成的數(shù)列，接下來有 m 次操作，分別對應(yīng)著區(qū)間查詢最大值以及單點(diǎn)修改，實(shí)現(xiàn) m 次操作
題目分析：線段樹裸題，就不多說了，Splay的話，就在每個(gè)節(jié)點(diǎn)再維護(hù)一個(gè) val 和一個(gè) mmax 分別代表點(diǎn)權(quán)和子樹的最大值，單點(diǎn)修改很簡單，只需要找到對應(yīng)的節(jié)點(diǎn)修改權(quán)值就好了，而區(qū)間查詢也非常的巧妙，首先將 l - 1 這個(gè)節(jié)點(diǎn)旋到根節(jié)點(diǎn) 處，這樣根節(jié)點(diǎn)的右子樹中的所有節(jié)點(diǎn)的下標(biāo)都一定比 l - 1 大了，此時(shí)再把 r + 1 這個(gè)節(jié)點(diǎn)旋到根節(jié)點(diǎn)的右兒子 處，根據(jù)SBT的性質(zhì)可知，此時(shí)根節(jié)點(diǎn)的右兒子的左子樹 中的所有節(jié)點(diǎn)一定都屬于 [ l , r ] 這個(gè)區(qū)間中了，因?yàn)?mmax 維護(hù)的是子樹中的最大值，所以答案就是根節(jié)點(diǎn)的右兒子的左兒子 的 mmax 了
非常巧妙的思想，利用Slpay實(shí)現(xiàn)了區(qū)間查詢的功能，時(shí)間復(fù)雜度均攤下來也是 logn ，不過唯一的要求就是需要自己動手對模板內(nèi)部實(shí)現(xiàn)進(jìn)行一定量的修改，從而滿足自己的需求，這就需要對模板的理解有著一定程度的要求了
代碼：
#include<iostream>
#include<cstdio>
#include<string>
#include<ctime>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<stack>
#include<climits>
#include<queue>
#include<map>
#include<set>
#include<sstream>
using namespace std;typedef long long LL;typedef unsigned long long ull;const int inf=0x3f3f3f3f;const int N=2e5+100;class Splay//存儲規(guī)則：小左大右，重復(fù)節(jié)點(diǎn)記錄
{#define root e[0].ch[1] //該樹的根節(jié)點(diǎn)private:class node{public:int mmax;int val;int v,father;//節(jié)點(diǎn)值，父級節(jié)點(diǎn) int ch[2];//左孩子=0，右孩子=1int sum;//自己+自己下級有多少節(jié)點(diǎn)。在根節(jié)點(diǎn)為1。int recy;//記錄自己被重復(fù)了幾次};node e[N];//Splay樹主體int n,points;//使用存儲數(shù),元素?cái)?shù)void update(int x){e[x].sum=e[e[x].ch[0]].sum+e[e[x].ch[1]].sum+e[x].recy;e[x].mmax=max(max(e[e[x].ch[0]].mmax,e[e[x].ch[1]].mmax),e[x].val);}int identify(int x){return e[e[x].father].ch[0]==x?0:1;}void connect(int x,int f,int son)//連接函數(shù)。用法：connect(son,father,1/0){e[x].father=f;e[f].ch[son]=x;}//作用：使得x的father=f，f的son=x.void rotate(int x){int y=e[x].father;int mroot=e[y].father;int mrootson=identify(y);int yson=identify(x);int B=e[x].ch[yson^1];connect(B,y,yson);connect(y,x,(yson^1));connect(x,mroot,mrootson);update(y);update(x);}void splay(int at,int to)//將at位置的節(jié)點(diǎn)移動到to位置{to=e[to].father;while(e[at].father!=to){int up=e[at].father;if(e[up].father==to) rotate(at);else if(identify(up)==identify(at)){rotate(up);rotate(at);}else{rotate(at);rotate(at);}}}int crepoint(int v,int father,int num){n++;e[n].v=v;e[n].father=father;e[n].sum=e[n].recy=1;e[n].val=num;e[n].mmax=num;e[n].ch[0]=e[n].ch[1]=0;return n;}void destroy(int x)//pop后摧毀節(jié)點(diǎn) {e[x].v=e[x].ch[0]=e[x].ch[1]=e[x].sum=e[x].father=e[x].recy=0;if(x==n) n--;//最大限度優(yōu)化}public:void init(){points=n=root=0;e[root].v=e[root].father=e[root].sum=e[root].recy=e[root].val=e[root].mmax=e[root].ch[0]=e[root].ch[1]=0;}int getroot(){return root;}int find(int v)//用于外部的find調(diào)用{int now=root;while(true){if(e[now].v==v){
// splay(now,root);return now;}int next=v<e[now].v?0:1;if(!e[now].ch[next]) return 0;now=e[now].ch[next];}}int build(int v,int num)//內(nèi)部調(diào)用的插入函數(shù)，沒有splay {points++;if(points==1)//特判無點(diǎn)狀態(tài) {root=n+1;crepoint(v,0,num);}else{int now=root;while(true)//向下找到一個(gè)空節(jié)點(diǎn) {e[now].sum++;//自己的下級肯定增加了一個(gè)節(jié)點(diǎn) if(v==e[now].v){e[now].recy++;return now;}int next=v<e[now].v?0:1;if(!e[now].ch[next]){crepoint(v,now,num);e[now].ch[next]=n;return n;}now=e[now].ch[next];}}return 0;}void push(int v,int num)//插入元素時(shí)，先添加節(jié)點(diǎn)，再進(jìn)行伸展 {int add=build(v,num);splay(add,root);}void pop(int v)//刪除節(jié)點(diǎn) {int deal=find(v);if(!deal) return;points--;if(e[deal].recy>1){e[deal].recy--;e[deal].sum--;return;}if(!e[deal].ch[0]){root=e[deal].ch[1];e[root].father=0;}else{int lef=e[deal].ch[0];while(e[lef].ch[1]) lef=e[lef].ch[1];splay(lef,e[deal].ch[0]);int rig=e[deal].ch[1];connect(rig,lef,1);connect(lef,0,1);update(lef);}destroy(deal);}int rank(int v)//獲取值為v的元素在這棵樹里是第幾小 {int ans=0,now=root;while(true){if(e[now].v==v) {ans+=e[e[now].ch[0]].sum;splay(now,root);return ans+1;}if(now==0) return 0;if(v<e[now].v) now=e[now].ch[0];else{ans=ans+e[e[now].ch[0]].sum+e[now].recy;now=e[now].ch[1];}}return 0;}int atrank(int x)//獲取第x小的元素的值 {if(x>points) return -inf;int now=root;while(true){int minused=e[now].sum-e[e[now].ch[1]].sum;if(x>e[e[now].ch[0]].sum&&x<=minused) break;if(x<minused) now=e[now].ch[0];else{x=x-minused;now=e[now].ch[1];}}splay(now,root);return e[now].v;}int upper(int v)//尋找該值對應(yīng)的一個(gè)最近的上界值 {int now=root;int result=inf;while(now){if(e[now].v>=v&&e[now].v<result) result=e[now].v;if(v<e[now].v) now=e[now].ch[0];else now=e[now].ch[1];}return result;}int lower(int v)//尋找該值對應(yīng)的一個(gè)最近的下界值 {int now=root;int result=-inf;while(now){if(e[now].v<=v&&e[now].v>result) result=e[now].v;if(v>e[now].v) now=e[now].ch[1];else now=e[now].ch[0];}return result;}void UPDATE(int pos,int val){splay(find(pos),root);//旋到根 e[root].val=val;e[root].mmax=max(max(e[e[root].ch[0]].mmax,e[e[root].ch[1]].mmax),val);}int query(int l,int r){splay(find(l-1),root);splay(find(r+1),e[root].ch[1]);return e[e[e[root].ch[1]].ch[0]].mmax;}#undef root
}tree;int main()
{
#ifndef ONLINE_JUDGE
// freopen("input.txt","r",stdin);
// freopen("output.txt","w",stdout);
#endif
// ios::sync_with_stdio(false);int n,m;while(scanf("%d%d",&n,&m)!=EOF){tree.init();tree.push(0,-inf);for(int i=1;i<=n;i++){int num;scanf("%d",&num);tree.push(i,num);}tree.push(n+1,-inf);while(m--){char op[5];scanf("%s",op);if(op[0]=='U'){int pos,val;scanf("%d%d",&pos,&val);tree.UPDATE(pos,val);}else{int l,r;scanf("%d%d",&l,&r);printf("%d\n",tree.query(l,r));}}}return 0;
}
?
總結(jié)
以上是生活随笔 為你收集整理的HDU - 1754 I Hate It(Splay-区间最大值) 的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔 網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔 推薦給好友。
