1.注意在 split 和 merge时要特判一下边界, 否则就会出现边界错误的情况。

2.随时都要维护父指针。
3.在更新 maxv
 和翻转标记时要判一下左右儿子是否都存在。

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn = 100000 + 3;
int f[maxn], ch[maxn][2], n,m,numv[maxn], maxv[maxn], siz[maxn], tag[maxn], root, cnt , lazy[maxn];
struct Operation
{
inline int get(int x){ return ch[f[x]][1] == x; }
inline void pushdown(int x)
{
if(tag[x])
{
swap(ch[ch[x][0]][0],ch[ch[x][0]][1]);
swap(ch[ch[x][1]][0],ch[ch[x][1]][1]);
if(ch[x][0]) tag[ch[x][0]] ^= 1;
if(ch[x][1]) tag[ch[x][1]] ^= 1;
tag[x] = 0;
}
if(lazy[x])
{
if(ch[x][0]) maxv[ch[x][0]] += lazy[x], lazy[ch[x][0]] += lazy[x], numv[ch[x][0]] += lazy[x];
if(ch[x][1]) maxv[ch[x][1]] += lazy[x], lazy[ch[x][1]] += lazy[x], numv[ch[x][1]] += lazy[x];
lazy[x] = 0;
}
}
inline void pushup(int x)
{
siz[x] = siz[ch[x][0]] + siz[ch[x][1]] + 1;
maxv[x] = numv[x];
if(ch[x][0]) maxv[x] = max(maxv[x], maxv[ch[x][0]]);
if(ch[x][1]) maxv[x] = max(maxv[x], maxv[ch[x][1]]);
}
inline void rotate(int x)
{
int old = f[x], oldf = f[old], which = get(x);
ch[old][which] = ch[x][which ^ 1], f[ch[old][which]] = old;
ch[x][which ^ 1] = old, f[old] = x, f[x] = oldf;
if(oldf) ch[oldf][ch[oldf][1] == old] = x;
pushup(old); pushup(x);
}
inline void splay(int x,int &tar)
{
int a = f[tar];
for(int fa; (fa = f[x]) != a; rotate(x))
if(f[fa] != a) rotate(get(x) == get(fa) ? fa : x);
tar = x;
}
inline int findx(int x, int top)
{
int cur = top;
while(x > 0)
{
pushdown(cur);
int ls = ch[cur][0], rs = ch[cur][1];
if(siz[ls] + 1 == x) return cur;
if(siz[ls] >= x) cur = ls;
else x -= siz[ls] + 1, cur = rs;
}
return 0;
}
inline void split(int &a,int nums,int &b)
{
if(nums == 0)
{
b = a, a = 0; return ;
}
if(nums == siz[a])
{
b = 0; return ;
}
int u = findx(nums, a);
splay(u, a);
b = ch[a][1];
f[ch[a][1]] = 0, ch[a][1] = 0,
pushup(a);
}
inline void merge(int &a,int b)
{
if(!a) { a = b; return ;}
splay(findx(siz[a], a), a);
ch[a][1] = b, f[b] = a;
pushup(a);
}
void build(int l,int r,int &o,int fa)
{
if(l > r) return ;
o = ++cnt;
f[o] = fa, siz[o] = 1;
int mid = (l + r) >> 1;
build(l, mid - 1, ch[o][0], o);
build(mid + 1, r, ch[o][1], o);
pushup(o);
}
}T;
int main()
{
//freopen("input.txt","r",stdin);
scanf("%d%d",&n,&m);
T.build(1, n, root, 0);
while(m--)
{
int ops, l , r, v = 0;
scanf("%d%d%d",&ops,&l,&r);
int a = 0, b = 0;
T.split(root, l - 1, a);
T.split(a, r - l + 1, b);
if(ops == 1)
{
scanf("%d",&v);
maxv[a] += v, lazy[a] += v, numv[a] += v;
T.pushup(a);
}
if(ops == 2)
{
swap(ch[a][0], ch[a][1]);
tag[a] ^= 1;
}
if(ops == 3)
{
printf("%d\n",maxv[a]);
}
T.merge(root, a);
T.merge(root, b);
}
return 0;
}

  

最新文章

  1. 浅谈JDBC访问MySQL数据库
  2. Cannot set a credential for principal 'sa'. (Microsoft SQL Server,错误: 15535)
  3. Deployment failure on Tomcat 6.x. Could not copy all resources to……
  4. Android系统兼容性问题(持续更新)
  5. iOS 获取IP地址
  6. MIN (Transact-SQL)【转】
  7. gridview中使用href调用javascript
  8. BZOJ 2276 Temperature
  9. Myeclipse 搭建Java Web 项目 《一》
  10. 不可思议的纯 CSS 滚动进度条效果
  11. Lubuntu安装屏幕键盘onboard,使触摸屏可以登录和输入
  12. 详解Windows不重启使环境变量修改生效(经典)
  13. synchronized细节问题(二)
  14. Android通用简洁的下载器
  15. 使用EntityManager批量保存数据
  16. html5式程序员表白
  17. C#学习笔记(13)——传统方法读取XML
  18. SQL 2008维护计划不执行的问题
  19. 【BZOJ】1798: [Ahoi2009]Seq 维护序列seq 线段树多标记(区间加+区间乘)
  20. js正则表达式验证大全--转载

热门文章

  1. mysql deadlock、Lock wait timeout解决和分析
  2. 0709关于mysql优化思路【何登成】
  3. CODEVS——T 2618 核电站问题
  4. uva:10763 - Foreign Exchange(排序)
  5. TagCloud with xml
  6. Android基础新手教程——3.4 TouchListener PK OnTouchEvent + 多点触碰
  7. SQL SERVER的浮点数类型及与C#的对应关系
  8. 控制台中使用SetTimer的提醒
  9. UVa 572 - Oil Deposits (简单dfs)
  10. C语言 - .c和.h文件的困惑