HDU5367 – digger(动态线段树)

HDU5367

【题意】中文链接

【分析】线段树方法很容易想到,维护区间左边连续相同的值,左边连续相同的长度,区间左边长度尽头右边的值;然后右边一样反过来,再加个lazy标记。但是一看n有10^9,而又是强制在线(如果可以离线只要离散就好了),以前脑子里面默认线段树一样要初始化的时候就把所有结点都建好,其实只要像主席树那样,需要用的时候再新建,否则不建,开始只要一个根结点记录1~n就好了,这样为什么不爆内存?因为只有50000个查询,而每次查询最多新建logn个结点(如果全部结点都建出来需要2*n个结点显然是不行的),所以总的结点数不会超过q*logn个。

【AC CODE】592ms

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
#define rep(i,a,n) for(int i = a; i < n; i++)
#define repe(i,a,n) for(int i = a; i <= n; i++)
#define per(i,n,a) for(int i = n; i >= a; i--)
#define clc(a,b) memset(a,b,sizeof(a))
const int INF = 0x3f3f3f3f, MAXN = 50000+10, MAXBUF = 10000, MAXOUT = 10000;
char buf[MAXBUF], *ps = buf, *pe = buf+1;
inline void rnext(){
	if(++ps == pe)
		pe = (ps = buf)+fread(buf,sizeof(char),sizeof(buf)/sizeof(char),stdin);
}
template <class T>
inline bool in(T &ans)
{
	ans = 0;
	T f = 1;
	if(ps == pe) return false;//EOF
	do{
		rnext();
		if('-' == *ps) f = -1;
	}while(!isdigit(*ps) && ps != pe);
	if(ps == pe) return false;//EOF
	do
	{
		ans = (ans<<1)+(ans<<3)+*ps-48;
		rnext();
	}while(isdigit(*ps) && ps != pe);
	ans *= f;
	return true;
}
char bufout[MAXOUT], outtmp[50],*pout = bufout, *pend = bufout+MAXOUT;
inline void write()
{
	fwrite(bufout,sizeof(char),pout-bufout,stdout);
	pout = bufout;
}
inline void out_char(char c){ *(pout++) = c;if(pout == pend) write();}
inline void out_str(char *s)
{
	while(*s)
	{
		*(pout++) = *(s++);
		if(pout == pend) write();
	}
}
template <class T>
inline void out_int(T x) {
	if(!x)
	{
		out_char('0');
		return;
	}
	if(x < 0) x = -x,out_char('-');
	int len = 0;
	while(x)
	{
		outtmp[len++] = x%10+48;
		x /= 10;
	}
	outtmp[len] = 0;
	for(int i = 0, j = len-1; i < j; i++,j--) swap(outtmp[i],outtmp[j]);
	out_str(outtmp);
}
struct NODE{
	int x,y,lc,rc;
	int sum,lh,llen,rh,rlen, nlh,nrh,add;
}node[MAXN*30];
int r,tol;
void init(NODE &p, int x, int y)
{
	p.x = x, p.y = y;
	p.lc = p.rc = -1;
	p.llen = p.rlen = y-x+1;
	p.lh = p.rh = r;
	p.nlh = p.nrh = INF;
	p.sum = p.add = 0;
}
int newnode(int x, int y)
{
	init(node[tol],x,y);
	return tol++;
}
void add_one(NODE &p, int v)
{
	p.lh += v;p.rh += v;
	if(p.nlh != INF) p.nlh += v;
	if(p.nrh != INF) p.nrh += v;
	p.add += v;
}
void push_down(NODE &p, int m)
{
	if(p.add)
	{
		if(-1 == p.lc) p.lc = newnode(p.x,m);
		if(-1 == p.rc) p.rc = newnode(m+1,p.y);
		add_one(node[p.lc],p.add);
		add_one(node[p.rc],p.add);
		p.add = 0;
	}
}
void push_up(int u, int &ll, int &rr, int m)
{
	NODE &p = node[u];
	if(-1 == ll) ll = newnode(p.x,m);
	if(-1 == rr) rr = newnode(m+1,p.y);
	NODE &l = node[ll], &r = node[rr];
	p.sum = l.sum+r.sum;
	if(l.rh == r.lh)
	{
		if(l.rlen != l.y-l.x+1 && r.llen != r.y-r.x+1 && l.rh > l.nrh && r.lh > r.nlh) p.sum += l.rlen+r.llen;
	}
	else
	{
		if(l.rlen != l.y-l.x+1 && l.rh > r.lh && l.rh > l.nrh) p.sum += l.rlen;
		if(r.llen != r.y-r.x+1 && r.lh > l.rh && r.lh > r.nlh) p.sum += r.llen;
	}
	p.lh = l.lh;p.rh = r.rh;
	p.llen = l.llen;p.rlen = r.rlen;
	if(l.llen == l.y-l.x+1 && l.rh == r.lh) p.llen += r.llen;
	if(r.rlen == r.y-r.x+1 && l.rh == r.lh) p.rlen += l.rlen;
	if(l.llen != l.y-l.x+1) p.nlh = l.nlh;
	else
	{
		if(l.rh == r.lh) p.nlh = r.nlh;
		else p.nlh = r.lh;
	}
	if(r.rlen != r.y-r.x+1) p.nrh = r.nrh;
	else
	{
		if(l.rh == r.lh) p.nrh = l.nrh;
		else p.nrh = l.rh;
	}
	if(p.llen == p.y-p.x+1) p.nrh = INF;
	if(p.rlen == p.y-p.x+1) p.nlh = INF;
}
void update(int& rt, int x, int y, int ql, int qr, int v)
{
	if(-1 == rt) rt = newnode(x,y);
	if(ql <= x && y <= qr)
	{
		add_one(node[rt],v);
		return;
	}
	int m = (x+y)>>1;
	push_down(node[rt],m);
	if(ql <= m) update(node[rt].lc,x,m,ql,qr,v);
	if(qr > m) update(node[rt].rc,m+1,y,ql,qr,v);
	push_up(rt,node[rt].lc,node[rt].rc,m);
}

int main()
{
#ifdef SHY
	freopen("d:\\1.txt", "r", stdin);
#endif
	int n,q;
	while(in(n))
	{
		in(q);in(r);
		tol = 1;
		init(node[0],1,n);
		int rt = 0;
		int ans = 0;
		while(q--)
		{
			int x,y,v;
			in(x);in(y);in(v);
			x ^= ans, y ^= ans, v ^= ans;
			update(rt,1,n,x,y,v);
			ans = node[0].sum;
			out_int(ans);out_char('\n');
		}
	}
	write();
	return 0;
}

 

发表评论

邮箱地址不会被公开。 必填项已用*标注

请输入正确的验证码