小鱼儿网站做啥用的,重庆网站建设吧,一级域名网站怎样收费的,建筑网站图片传送门 文章目录题意#xff1a;思路#xff1a;题意#xff1a; 思路#xff1a;
很明显的数据结构了#xff0c;splaysplaysplay当然能写#xff0c;但是fhq−treapfhq-treapfhq−treap更加简洁易懂。 考虑第一个操作#xff0c;无非就是分裂出[1,pos−1][1,pos-1][1…传送门
文章目录题意思路题意 思路
很明显的数据结构了splaysplaysplay当然能写但是fhq−treapfhq-treapfhq−treap更加简洁易懂。 考虑第一个操作无非就是分裂出[1,pos−1][1,pos-1][1,pos−1]与[pos,n][pos,n][pos,n]让后再新建一个节点nownownow将[1,pos−1],now,[pos,n][1,pos-1],now,[pos,n][1,pos−1],now,[pos,n]合并起来就好了。 第二个操作分裂出[l,r][l,r][l,r]的区间让后更新即可。 第三个操作分裂出[l,r][l,r][l,r]的区间输出sumsumsum即可。
需要注意的点 (1)(1)(1)每次分裂后都别忘记mergemergemerge。 (2)(2)(2)上传信息的时候sumsumsum别忘记加上当前子树根的valvalval道理跟sizesizesize一样。 (3)(3)(3)懒标记更新的时候别忘记更新valvalval。
这里采用了笛卡尔树建树O(n)O(n)O(n)的方式以及直接建树O(nlogn)O(nlogn)O(nlogn)的方式。
//#pragma GCC optimize(Ofast,no-stack-protector,unroll-loops,fast-math)
//#pragma GCC target(sse,sse2,sse3,ssse3,sse4.1,sse4.2,avx,avx2,popcnt,tunenative)
//#pragma GCC optimize(2)
#includecstdio
#includeiostream
#includestring
#includecstring
#includemap
#includecmath
#includecctype
#includevector
#includeset
#includequeue
#includealgorithm
#includesstream
#includectime
#includecstdlib
#define X first
#define Y second
#define L (u1)
#define R (u1|1)
#define pb push_back
#define mk make_pair
#define Mid (tr[u].ltr[u].r1)
#define Len(u) (tr[u].r-tr[u].l1)
#define random(a,b) ((a)rand()%((b)-(a)1))
#define db puts(---)
using namespace std;//void rd_cre() { freopen(d://dp//data.txt,w,stdout); srand(time(NULL)); }
//void rd_ac() { freopen(d://dp//data.txt,r,stdin); freopen(d://dp//AC.txt,w,stdout); }
//void rd_wa() { freopen(d://dp//data.txt,r,stdin); freopen(d://dp//WA.txt,w,stdout); }typedef long long LL;
typedef unsigned long long ULL;
typedef pairint,int PII;const int N1000010,mod1e97,INF0x3f3f3f3f;
const double eps1e-6;int n,m,x,y,z,root,tot;
int stk[N];
struct Node {int l,r;int size,rank;LL sum,lazy,val;
}tr[N2];int newnode(int val) {int utot;tr[u].valtr[u].sumval; tr[u].rankrand();tr[u].size1;tr[u].ltr[u].rtr[u].lazy0;return u;
}void pushup(int u) {tr[u].sumtr[tr[u].l].sumtr[tr[u].r].sumtr[u].val;tr[u].sizetr[tr[u].l].sizetr[tr[u].r].size1;
}void pushdown(int u) {if(tr[u].lazy!0) {LL lazytr[u].lazy; tr[u].lazy0;int lstr[u].l,rstr[u].r;tr[ls].sumtr[ls].size*lazy; tr[ls].lazylazy; tr[ls].vallazy;tr[rs].sumtr[rs].size*lazy; tr[rs].lazylazy; tr[rs].vallazy;}
}void split(int u,int k,int x,int y) {if(!u) { xy0; return; }pushdown(u);if(ktr[tr[u].l].size) yu,split(tr[u].l,k,x,tr[u].l);else xu,split(tr[u].r,k-tr[tr[u].l].size-1,tr[u].r,y);pushup(u);
}int merge(int u,int v) {if(!u||!v) return uv;if(tr[u].ranktr[v].rank) {pushdown(u);tr[u].rmerge(tr[u].r,v);pushup(u);return u;}else {pushdown(v);tr[v].lmerge(u,tr[v].l);pushup(v);return v;}
}void build() {int cur0,top0;for(int i1;in;i) {int val; scanf(%d,val);int nownewnode(val);curtop;while(curtr[stk[cur]].ranktr[now].rank) pushup(stk[cur]),cur--;if(cur) tr[stk[cur]].rnow,pushup(stk[cur]);if(curtop) tr[now].lstk[cur1],pushup(now);stk[cur]i; topcur;}while(top) pushup(stk[top--]);rootstk[1];
}void dfs(int u) {if(tr[u].l) dfs(tr[u].l);if(u) printf(%d ,tr[u].val);if(tr[u].r) dfs(tr[u].r);
}int main()
{
// ios::sync_with_stdio(false);
// cin.tie(0);scanf(%d,n);build();/*for(int i1;in;i) {int val; scanf(%d,val);rootmerge(root,newnode(val));}*/int q; scanf(%d,q);while(q--) {int op; scanf(%d,op);if(op1) {int pos; scanf(%d,pos);split(root,pos-1,x,y);rootmerge(merge(x,newnode(0)),y);}else if(op2) {int l,r,val; scanf(%d%d%d,l,r,val);split(root,r,x,y); split(x,l-1,x,z);tr[z].sum1ll*tr[z].size*val; tr[z].lazyval;tr[z].valval;rootmerge(merge(x,z),y);}else {int l,r; scanf(%d%d,l,r);split(root,r,x,y); split(x,l-1,x,z);printf(%lld\n,tr[z].sum);rootmerge(merge(x,z),y);}} return 0;
}
/**/
