[NOI2005]維護數列 惡心到毀天滅地的splay

?傳送門 ?

debug到死2333.

雖然說是splay維護序列模板,作為蒟蒻的我還是GG

%%%考場A的dalao Orz ?Orz.

其實不開long long也行,inf開成0x3f3f3f3f也可(flag,歡迎推翻)

就當存個板子吧.

#include<bits/stdc++.h>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<queue>
#include<deque>
#include<list>
#include<set>
#include<vector>
#include<iostream>
#define ll long long
#define re register
#define inf 0x7f7f7f7f
#define inl inline
#define sqr(x) (x*x)
#define max(a,b) (a>b?a:b)
//#define eps 1e-8
#define debug puts("**************************");
//#pragma comment(linker, "/STACK:1024000000,1024000000")
//#pragma GCC optimize (2)
//#pragma G++ optimize (2)
using namespace std;
//const ll mod;
const ll MAXN=1e6+10;
inl ll read() {re ll x = 0; re int f = 1;char ch = getchar();while(ch<'0'||ch>'9') { if(ch== '-' ) f = -1; ch = getchar(); }while(ch>='0'&&ch<='9') {x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x * f;
}
inl char readc() {char ch=getchar();while(('z'<ch||ch<'a')&&('Z'<ch||ch<'A')) ch=getchar();return ch;
}
inl void write(re ll x){if(x>=10)write(x/10);putchar(x%10+'0');
}
inl void writeln(re ll x){if(x<0) {x=-x;putchar('-');}write(x); puts("");
}
inl ll gcd(re ll x,re ll y){while(y^=x^=y^=x%=y);return x;}
inl ll Lcm(re ll a,re ll b) {return a/gcd(a,b)*b;}
inl void FR() {freopen(".in","r",stdin);freopen(".out","w",stdout);
}
inl void FC() {fclose(stdin);fclose(stdout);
}
ll root,id[MAXN],cnt;
struct Node {ll fa,son[2],sumx,val,siz,maxx,lx,rx;bool rev,flag;void clear() {fa=son[0]=son[1]=sumx=val=siz=maxx=lx=rx=rev=flag=0;}
}Tree[MAXN];
ll dir(ll x) {return Tree[Tree[x].fa].son[1]==x;}
inl void pushup(ll x) {re ll l=Tree[x].son[0],r=Tree[x].son[1];Tree[x].siz=Tree[l].siz+Tree[r].siz+1;Tree[x].sumx=Tree[l].sumx+Tree[r].sumx+Tree[x].val;Tree[x].maxx=max(Tree[r].maxx,Tree[l].maxx);Tree[x].maxx=max(Tree[x].maxx,Tree[l].rx+Tree[r].lx+Tree[x].val);Tree[x].lx=max(Tree[l].lx,Tree[l].sumx+Tree[x].val+Tree[r].lx);Tree[x].rx=max(Tree[r].rx,Tree[r].sumx+Tree[x].val+Tree[l].rx);
}
inl void pushdown(ll x) {re ll l=Tree[x].son[0],r=Tree[x].son[1];if(Tree[x].flag) {Tree[x].flag=Tree[x].rev=0;if(l) Tree[l].val=Tree[x].val,Tree[l].sumx=Tree[l].val*Tree[l].siz,Tree[l].flag=1;if(r) Tree[r].val=Tree[x].val,Tree[r].sumx=Tree[r].val*Tree[r].siz,Tree[r].flag=1;if(Tree[x].val>=0) {if(l) Tree[l].lx=Tree[l].rx=Tree[l].maxx=Tree[l].sumx;if(r) Tree[r].lx=Tree[r].rx=Tree[r].maxx=Tree[r].sumx;}else {if(l) Tree[l].lx=Tree[l].rx=0,Tree[l].maxx=Tree[l].val;if(r) Tree[r].lx=Tree[r].rx=0,Tree[r].maxx=Tree[r].val;}}if(Tree[x].rev) {Tree[x].rev=0;Tree[l].rev^=1;Tree[r].rev^=1;swap(Tree[l].lx,Tree[l].rx);swap(Tree[r].lx,Tree[r].rx);swap(Tree[l].son[0],Tree[l].son[1]);swap(Tree[r].son[0],Tree[r].son[1]);}
}
inl void rotate(ll x) {re ll y=Tree[x].fa,z=Tree[y].fa,o=dir(x);re ll so=dir(y);Tree[y].son[o]=Tree[x].son[o^1];Tree[Tree[y].son[o]].fa=y;Tree[x].son[o^1]=y;Tree[y].fa=x;Tree[z].son[so]=x;Tree[x].fa=z;pushup(y);pushup(x);
}
inl void splay(ll x,ll goal) {for(re ll y;(y=Tree[x].fa)!=goal;rotate(x)) {if(Tree[y].fa!=goal) rotate(dir(y)==dir(x)?y:x);}if(!goal) root=x;
}
inl ll find(ll x,ll rk) {pushdown(x);re ll l=Tree[x].son[0],r=Tree[x].son[1];if(Tree[l].siz+1==rk) return x;else if(Tree[l].siz>=rk) return find(l,rk);else return find(r,rk-Tree[l].siz-1);
}
ll s[MAXN];
inl ll build(ll l,ll r,ll fro) {re ll mid=(l+r)>>1,t=id[mid];Tree[t].clear();Tree[t].val=s[mid];Tree[t].fa=fro;if(l==r) {Tree[t].lx=Tree[t].rx=max(0,Tree[t].val);Tree[t].maxx=Tree[t].sumx=Tree[t].val;Tree[t].son[0]=Tree[t].son[1]=0;Tree[t].siz=1;return t;}if(l<mid) Tree[t].son[0]=build(l,mid-1,t);else Tree[t].son[0]=0;if(mid<r) Tree[t].son[1]=build(mid+1,r,t);else Tree[t].son[1]=0;pushup(t);return t;
}
char ss[20];
queue<ll>Q;
inl void insert(ll pos,ll tot) {for(re ll i=1;i<=tot;i++) s[i]=read();for(re ll i=1;i<=tot;i++) {if(!Q.empty()) id[i]=Q.front(),Q.pop();else id[i]=++cnt;}re ll l=find(root,pos+1),r=find(root,pos+2);splay(l,0);splay(r,l);Tree[r].son[0]=build(1,tot,r);pushup(r);pushup(l);
}
inl void recycle(ll x) {re ll &l=Tree[x].son[0],&r=Tree[x].son[1];if(l) recycle(l);if(r) recycle(r);Q.push(x);Tree[x].clear();l=r=0;
}
inl ll split(ll pos,ll tot) {re ll x=find(root,pos),y=find(root,pos+tot+1);splay(x,0);splay(y,x);return Tree[y].son[0];
}
inl void del(ll pos,ll tot) {re ll x=split(pos,tot),y=Tree[x].fa;recycle(x);Tree[y].son[0]=0;pushup(y);pushup(Tree[y].fa);
}
inl void modify(ll pos,ll tot,ll val) {re ll x=split(pos,tot),y=Tree[x].fa;Tree[x].flag=1;Tree[x].val=val,Tree[x].sumx=Tree[x].siz*Tree[x].val;if(Tree[x].val>=0) Tree[x].lx=Tree[x].rx=Tree[x].maxx=Tree[x].sumx;else Tree[x].lx=Tree[x].rx=0,Tree[x].maxx=Tree[x].val;pushup(y);pushup(Tree[y].fa);
}
inl void rever(ll pos,ll tot) {re ll x=split(pos,tot),y=Tree[x].fa;if(!Tree[x].flag) {Tree[x].rev^=1;swap(Tree[x].lx,Tree[x].rx);swap(Tree[x].son[0],Tree[x].son[1]);pushup(y);pushup(Tree[y].fa);}
}
inl ll query(ll pos,ll tot) {re ll x=split(pos,tot);return Tree[x].sumx;
}
int main() {
//  FR();re ll n=read(),m=read();for(re ll i=1;i<=n;i++) {s[i+1]=read();}Tree[0].maxx=s[1]=s[n+2]=-inf;cnt=n+2;for(re ll i=1;i<=n+2;i++) id[i]=i;root=build(1,n+2,0);for(re ll i=1;i<=m;i++) {scanf("%s",ss);if(ss[0]=='I') {re ll pos=read(),tot=read();insert(pos,tot);}else if(ss[0]=='D') {re ll pos=read(),tot=read();del(pos,tot);}else if(ss[0]=='M') {if(ss[2]=='X') writeln(Tree[root].maxx);else {re ll pos=read(),tot=read(),val=read();modify(pos,tot,val);}}else if(ss[0]=='R') {re ll pos=read(),tot=read();rever(pos,tot);}else if(ss[0]=='G') {re ll pos=read(),tot=read();writeln(query(pos,tot));}}
//  FC();return 0;
}

?

轉載于:https://www.cnblogs.com/20020723YJX/p/9520947.html

本文來自互聯網用戶投稿,該文觀點僅代表作者本人,不代表本站立場。本站僅提供信息存儲空間服務,不擁有所有權,不承擔相關法律責任。
如若轉載,請注明出處:http://www.pswp.cn/news/451542.shtml
繁體地址,請注明出處:http://hk.pswp.cn/news/451542.shtml
英文地址,請注明出處:http://en.pswp.cn/news/451542.shtml

如若內容造成侵權/違法違規/事實不符,請聯系多彩編程網進行投訴反饋email:809451989@qq.com,一經查實,立即刪除!

相關文章

Python的from import和import的區別

對于from...import...&#xff0c;其意義具體是from Module import Function或Class等&#xff0c;這個只是從模塊中導入一個或幾個函數或類的做法。另外一個常見的是import Module&#xff0c;就是把整個模塊中得東西都導入&#xff0c;所以你后面的程序就都可以使用了。另外還…

靜態代理、動態代理、AOP

參考文章&#xff1a; Java中的代理模式——靜態代理以及分析靜態代理的缺點 Java中動態代理的兩種方式JDK動態代理和cglib動態代理以及區別 Spring中的AOP以及切入點表達式和各種通知

Linux系統中解壓縮指令匯總

.tar 解包&#xff1a; tar xvf FileName.tar 打包&#xff1a;tar cvf FileName.tar DirName &#xff08;注&#xff1a;tar是打包&#xff0c;不是壓縮&#xff01;&#xff09; --------------------------------------------- .gz 解壓1&#xff1a;gunzip FileName.gz 解…

python中的@

函數修飾符 ‘’ 用做函數的修飾符&#xff0c;可以在模塊或者類的定義層內對函數進行修飾&#xff0c; 出現在函數定義的前一行&#xff0c;不允許和函數定義在同一行 一個修飾符就是一個函數&#xff0c;它將被修飾的函數作為參數&#xff0c;并返回修飾后的同名函數或其他可…

這樣想起...

前些天發現了一個巨牛的人工智能學習網站&#xff0c;通俗易懂&#xff0c;風趣幽默&#xff0c;忍不住分享一下給大家。點擊跳轉到教程。 // 看到一張精致的自然風景圖片&#xff0c;心生向往. 在海的一個小小角落邊&#xff0c;有一寓不很大的房子&#xff0c;暮色浸染的云彩…

python幾種括號表示的類型

python語言最常見的括號有三種&#xff0c;分別是&#xff1a;小括號( )、中括號[ ]和大括號&#xff08;也叫做花括號{ }&#xff09;。其作用也各不相同&#xff0c;分別用來代表不同的python基本內置數據類型。 1、python中的小括號( )&#xff1a;代表tuple元組數據類型&am…

IT巨頭互掐云存儲:Dropbox能否一馬當先

隨著北京時間4月25日Google Drive橫空出世&#xff0c;微軟也迫不及待的發布了SkyDrive的大量更新。各大巨頭進軍云存儲市場&#xff0c;激烈角逐的意向已經昭然可見。網友針對此事紛紛發表熱議。蘋果、微軟、谷歌三巨頭加上一個Dropbox各出各的云存儲高招&#xff1a;微軟SkyD…

Spring集成redis(Spring Data Redis)

2019獨角獸企業重金招聘Python工程師標準>>> 轉載地址&#xff1a;http://blog.csdn.net/zhu_tianwei/article/details/44923001 Spring-data-redis是spring大家族的一部分&#xff0c;提供了在srping應用中通過簡單的配置訪問redis服務&#xff0c;對reids底層開發…

python中利用re模塊使用正則表達式

Python通過re模塊提供對正則表達式的支持。使用re的一般步驟是先使用re.compile()函數&#xff0c;將正則表達式的字符串形式編譯為Pattern實例&#xff0c;然后使用Pattern實例處理文本并獲得匹配結果&#xff08;一個Match實例&#xff09;&#xff0c;最后使用Match實例獲得…

Java三大變量分別是類變量、實例變量和局部變量

什么是變量:就是內容可以改變的量&#xff0c;它與常量相對應。而這三大變量實際上是從變量的作用域來定義和劃分的。 1、類變量&#xff0c;是歸屬類的變量&#xff0c;它是通過在定義類的屬性的時&#xff0c;增加static修飾符&#xff0c;所以又稱為靜態變量。類變量不僅可…

路途

前些天發現了一個巨牛的人工智能學習網站&#xff0c;通俗易懂&#xff0c;風趣幽默&#xff0c;忍不住分享一下給大家。點擊跳轉到教程。 PS : 這應該是08年寫的了吧.... 像是追尋明天的滄海一束&#xff0c; 不知道什么時候開始走上這樣熟悉的路途. 當天空開始一點一點變…

redux 源碼詳解

redux 單向數據流的由來 Flux將應用分成四個部分;view 視圖層;Action 視圖層發出的消息&#xff1b;(改變store里面的數據)Dispatch(派發器)Store (數據層) : 用來存在應用的狀態(數據)&#xff0c;一旦發生變動,就要提醒view更新頁面。redux單向數據流&#xff1a; 具體詳情請…

冒泡排序與快速排序(java實現)

冒泡排序&#xff1a; public class bubbleSort {public static void bubbleSort1(int [] a, int n){int i, j;for(i0; i<n; i){//表示 n 次排序過程。for(j1; j<n-i; j){if(a[j-1] > a[j]){//前面的數字大于后面的數字就交換//交換 a[j-1]和 a[j]int temp;temp a[j…

Python中文編碼問題詳解

中文編碼問題是用中文的程序員經常頭大的問題&#xff0c;在python下也是如此&#xff0c;那么應該怎么理解和解決python的編碼問題呢&#xff1f; 我們要知道python內部使用的是unicode編碼&#xff0c;而外部卻要面對千奇百怪的各種編碼&#xff0c;比如作為中國程序經常要…

PHP環境搭建和Apache HTTP服務器配置

所需軟件: 需要準備Apache HTTP 服務器: http://httpd.apache.org/download.cgi PHP環境下載:http://www.php.net/downloads.php Apache HTTP服務器安裝: 由于最新的 Apache 已經不提供 Windows 的安裝版本了&#xff0c;所以我們這里使用的是解壓版。 下載地址&#xff1a;htt…

ElasticSearch安裝過程中遇到的一些問題

問題1&#xff1a; 安裝Elasticsearch5.X版本&#xff0c;不修改默認配置的情況下&#xff0c;一切還好&#xff0c;能夠正常啟動。但我必須開通外網訪問。然后報錯了&#xff0c;報錯信息如下&#xff1a; ERROR: max file descriptors [1024] for elasticsearch process like…

Java原子操作類AtomicInteger應用場景

參考文章&#xff1a;Java原子操作類AtomicInteger應用場景 感謝作者分享&#xff01;

漂泊的足跡

前些天發現了一個巨牛的人工智能學習網站&#xff0c;通俗易懂&#xff0c;風趣幽默&#xff0c;忍不住分享一下給大家。點擊跳轉到教程。 似乎有河一樣的蔓延 流淌過我被陽光翻曬過的身軀 你的足跡 是遙遠的一個小島 從不知名的地方漂泊而來

什么是MD5

MD5是message-digest algorithm 5&#xff08;信息-摘要算法&#xff09;的縮寫&#xff0c;被廣泛用于加密和解密技術上&#xff0c;它可以說是文件的“數字指紋”。任何一個文件&#xff0c;無論是可執行程序、圖像文件、臨時文件或者其他任何類型的文件&#xff0c;也不管它…

selenium使用js進行點擊

WebElement button driver.findElement(By.xpath("/html/body/div[1]/div[3]/h2/div[2]")); JavascriptExecutor js (JavascriptExecutor) driver; js.executeScript("arguments[0].click();", button);當你使用driver原生API如果發現報錯&#xff0c;或…