P2042 [NOI2005]维护数列
题目的链接
众多平衡树独爱fhq
题目
有好多种操作：
1、添加一堆数
2、删除一个区间里的数
3、把一个区间里的数全变成同一个数
4、反转一个区间
5、求区间和
6、求最大的连续子序列的和。
因为要求连续的子序列的和，就想到了线段树区间合并。
这个，，应该可以想到。
所以就维护 lnum,rnum,num
做的时候的zz问题
崩溃了~~ 做的时候 我tmd 崩溃了，， 快神经了啊 我
一、添加一堆数我刚开始一个一个添加，， 因为方便（tle）
二、反转一个区间的时候没有反转lnum，rnum 这个问题很愚蠢，很快找到bug
三、update的时候没有判断左右子树是否存在。
四、空间不够用，没有弄回收节点的东西。
五、题意理解错了，一直卡一个点。最大的连续子序列的和不能不选，至少选一个数。wtmd一直以为可以不选，就是0。wtmdzz死了。
———————————假装分界线—————————————————
第一个问题好说，，用添加的点O(num)建一棵树再合并就好了。
第四个问题，删除的时候用一个栈存一下删除的节点，然后就好了。记得初始化！！！！ 初始化回收的那个节点。。 不然wa爆你！！！！！
第五个问题，主要是意识不到，，还是看了别人的代码才发现的，在题解区里看到跟我代码差不多的巨巨，，不然我就wa到明年了。
———————————假装分界线—————————————————
于是，上面的都改完还tle。。。
这就真的自闭了，，就差一点点，， 一丁点。。
于是，心态崩了，又交了一发原来的代码，就ac了。。。 可能因为随机数的问题？
好tmd搞心态啊。
代码
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <string>
#include <queue>
#include <cstring>
#include <stack>
#include <map>
#include <bitset>
#include <set>
#include <unordered_set>
#include <climits>
using namespace std;
typedef long long ll;
typedef pair<int,ll> pii;
typedef pair<ll,ll> pll;
typedef pair<double,double> pdd;
typedef unsigned long long ull;
typedef unordered_set<int>::iterator sit;
#define st first
#define sd second
#define mkp make_pair
#define pb push_back
void tempwj(){
freopen("hash.in","r",stdin);freopen("hash.out","w",stdout);}
ll gcd(ll a,ll b){
return b == 0 ? a : gcd(b,a % b);}
ll qpow(ll a,ll b,ll mod){
a %= mod;ll ans = 1;while(b > 0){
if(b & 1)ans = ans * a % mod;a = a * a % mod;b >>= 1;}return ans;}
struct cmp{
bool operator()(const pii & a, const pii & b){
return a.second > b.second;}};
int lb(int x){
return x & -x;}
//friend bool operator < (Node a,Node b) 重载
const int inf = INT_MAX;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const ll mod = 1e9+7;
const int maxn = 5e5+10;
const int M = 1e6 + 2;
// std::mt19937 rnd(233);
struct Node
{
int l,r,key;
int siz;
int val; // 当前节点的值
int lnum,rnum,num; // zuo you 最大连续
int sum;
int tag;
int tagf;
int f;
}node[maxn];
int cnt = 0;
int root = 0;
int sta[maxn];
int pos = 0;
int newnode(int val)
{
int p = 0;
if(pos >= 1)
{
p = sta[pos -- ];
// printf("%d 11111111\n",p);
}
else
p = ++cnt;
node[p].l = 0;
node[p].r = 0;
node[p].f = 0;
node[p].tagf = 0;
node[p].tag = 0;
node[p].val = val;
node[p].siz = 1;
node[p].key = rand();
// printf("%d\n",node[cnt].key);
node[p].lnum = node[p].rnum = node[p].num = max(val,0);
node[p].sum = val;
return p;
}
void update(int no)
{
if(node[no].l && node[no].r)
{
node[no].lnum = max(node[node[no].l].lnum,node[node[no].l].sum + node[no].val + node[node[no].r].lnum);
node[no].rnum = max(node[node[no].r].rnum,node[node[no].r].sum + node[no].val + node[node[no].l].rnum);
node[no].num = max(node[node[no].l].num,node[node[no].r].num);
node[no].num = max(node[no].num,node[node[no].l].rnum + node[node[no].r].lnum + node[no].val);
node[no].sum = node[node[no].l].sum + node[node[no].r].sum + node[no].val;
node[no].siz = node[node[no].l].siz + node[node[no].r].siz + 1;
}
else if(node[no].l)
{
node[no].lnum = max(node[node[no].l].lnum,node[no].val + node[node[no].l].sum);
node[no].rnum = max(0,node[no].val + node[node[no].l].rnum);
node[no].num = max(node[node[no].l].num,node[node[no].l].rnum + node[no].val);
node[no].sum = node[node[no].l].sum + node[no].val;
node[no].siz = node[node[no].l].siz + 1;
}
else if(node[no].r)
{
node[no].lnum = max(node[no].val + node[node[no].r].lnum, 0);
node[no].rnum = max(node[node[no].r].rnum,node[no].val + node[node[no].r].sum);
node[no].num = max(node[node[no].r].num,node[node[no].r].lnum + node[no].val);
node[no].sum = node[node[no].r].sum + node[no].val;
node[no].siz = node[node[no].r].siz + 1;
}
else
{
node[no].lnum = max(0,node[no].val);
node[no].rnum = max(0,node[no].val);
node[no].num = node[no].val;
node[no].sum = node[no].val;
node[no].siz = 1;
}
}
void Gai(int no,int num)
{
node[no].sum = node[no].siz * num;
node[no].val = num;
node[no].lnum = node[no].rnum = max(0,node[no].sum);
node[no].num = max(node[no].sum,node[no].val);
node[no].tag = num;
node[no].f = 1;
}
void Gai2(int no)
{
swap(node[no].l,node[no].r);
swap(node[no].lnum,node[no].rnum);
node[no].tagf ^= 1;
}
void down(int no)
{
if(node[no].f)
{
if(node[no].l)
Gai(node[no].l,node[no].tag);
if(node[no].r)
Gai(node[no].r,node[no].tag);
node[no].f = 0;
node[no].tag = 0;
}
if(node[no].tagf)
{
if(node[no].l)
Gai2(node[no].l);
if(node[no].r)
Gai2(node[no].r);
node[no].tagf = 0;
}
}
void split(int no,int& x,int& y,int siz)
{
if(no == 0)
{
x = 0;
y = 0;
return;
}
down(no);
if(node[node[no].l].siz + 1 <= siz)
{
x = no;
split(node[no].r,node[x].r,y,siz - node[node[no].l].siz - 1);
}
else
{
y = no;
split(node[no].l,x,node[no].l,siz);
}
update(no);
}
int merge(int x,int y)
{
if(x == 0 || y == 0)
return x + y;
if(node[x].key < node[y].key)
{
down(x);
node[x].r = merge(node[x].r,y);
update(x);
return x;
}
else
{
down(y);
node[y].l = merge(x,node[y].l);
update(y);
return y;
}
}
int a[maxn];
//模拟一个栈
int ss[maxn];
int build(int num)
{
int x = 0;
int last = 0;
int top = 0;
for (int i = 1; i <= num; i ++ )
{
x = newnode(a[i]);
last = 0;
while(top && node[ss[top]].key > node[x].key)
{
update(ss[top]);
last = ss[top];
ss[top -- ] = 0;
}
if(top)
{
node[ss[top]].r = x;
}
node[x].l = last;
ss[++top] = x;
}
while(top)
update(ss[top -- ]);
return ss[1];
}
void add(int pos,int num)
{
int x1,y1;
split(root,x1,y1,pos);
int t = build(num);
root = merge(x1,merge(t,y1));
}
void huishou(int no)
{
if(no == 0)
return;
sta[++pos] = no;
huishou(node[no].l);
huishou(node[no].r);
}
void del(int pos,int num)
{
int x1,y1;
split(root,x1,y1,pos);
int t;
split(y1,t,y1,num);
huishou(t);
root = merge(x1,y1);
}
void change(int l,int r,int num)
{
int x1,y1;
split(root,x1,y1,l - 1);
int x2,y2;
split(y1,x2,y2,r - l + 1);
if(x2)
Gai(x2,num);
root = merge(x1,merge(x2,y2));
}
void rev(int l,int r)
{
int x1,y1;
split(root,x1,y1,l - 1);
int x2,y2;
split(y1,x2,y2,r - l + 1);
if(x2)
Gai2(x2);
root = merge(x1,merge(x2,y2));
}
void zxbl(int no)
{
if(no == 0)
return;
zxbl(node[no].l);
printf("%d ",node[no].val);
zxbl(node[no].r);
}
int get_s(int l,int r)
{
int x1,y1;
split(root,x1,y1,l - 1);
int x2,y2;
split(y1,x2,y2,r - l + 1);
// zxbl(x2);
// printf("\n");
int ans = node[x2].sum;
root = merge(x1,merge(x2,y2));
return ans;
}
int main()
{
// tempwj();
int n,m;
scanf("%d%d",&n,&m);
for (int i = 1; i <= n; i ++ )
{
scanf("%d",&a[i]);
}
add(0,n);
// zxbl(root);
// printf("\n");
while(m -- )
{
char t[15];
scanf("%s",t + 1);
if(t[1] == 'G')
{
int x,y;
scanf("%d%d",&x,&y);
printf("%d\n",get_s(x,x + y - 1));
}
else if(t[1] == 'M' && t[3] == 'X')
{
printf("%d\n",node[root].num);
}
else if(t[1] == 'I')
{
int pos,p;
scanf("%d%d",&pos,&p);
for (int i = 1; i <= p; i ++ )
scanf("%d",&a[i]);
add(pos,p);
}
else if(t[1] == 'D')
{
int pos,p;
scanf("%d%d",&pos,&p);
del(pos - 1,p);
}
else if(t[1] == 'M' && t[3] == 'K')
{
int l,r,x;
scanf("%d%d%d",&l,&r,&x);
change(l,r + l - 1,x);
}
else if(t[1] == 'R')
{
int l,r;
scanf("%d%d",&l,&r);
rev(l,r + l - 1);
}
// zxbl(root);
// printf("%d\n",m);
}
}
京公网安备 11010502036488号