【题意】中文链接
【分析】线段树方法很容易想到,维护区间左边连续相同的值,左边连续相同的长度,区间左边长度尽头右边的值;然后右边一样反过来,再加个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; }