Sky 玩了一个神奇的游戏,这种游戏有n个集合,每一个集合内都可以插入数字。每一个集合都有一个权值,集合的权值定义为该集合内最长连续出现的数字个数。连续出现定义为: 如果[l,r]内的元素全部在该集合中存在, 那么这一部分是连续出现的,
连续的数字个数为r-l+1。
现在 Sky 准备开始玩这个集合,每一次 Sky 都会对一个区间的集合进行操作,一共操作m次。
每一次操作会输入l,r,x ,表示在第往l 到 r的集合都插入x这数字。
Sky 想知道,他的所有操作结束之后,所有集合的权值是什么。
输入两个数字n,m,然后输入m行l r x
输出n个数字,表示n个集合的权值
$ n,m \le 10^5 $
\(1 \le x \le 10^9\)
保证同一个数字不会重复插入一个集合
首先,区间加入一个数,有点像线段树,但是线段树每个节点代表一个元素,怎么代表一个集合??一个线段树只能表示一个集合,开n颗线段树?一次操作nlogn,无法接受。。
多颗线段树??主席树,线段树合并。。。
进一步分析,可以用线段树合并最后来统计答案。把x的值域当做线段树叶子节点个数,显然要离散化,但是跟一般的离散化又不一样,因为要判断离散化前的数字是不是相邻的,这需要特殊处理一下。区间操作可以用差分来代替,大大降低了时间复杂度。最后线段树维护区间最大连续数字长度即可。
这题y_dove大佬弱的时候用线段树分治过了,多了一个log,但是还是很快,std是线段树加STL一堆神奇操作,看不懂,空间比线段树合并优一点,但是比较慢。
#include<bits/stdc++.h> #define rep(i,j,k) for(register int i(j);i<=k;++i) #define drp(i,j,k) for(register int i(j);i>=k;--i) using namespace std; typedef long long lxl; template<typename T> inline T max(T &a, T &b) { return a > b ? a : b; } template<typename T> inline T min(T &a, T &b) { return a < b ? a : b; } inline char gt() { static char buf[1 << 21], *p1 = buf, *p2 = buf; return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++; } template <typename T> inline void read(T &x) { register char ch = gt(); x = 0; int w(0); while(!(ch >= '0' && ch <= '9'))w |= ch == '-', ch = gt(); while(ch >= '0' && ch <= '9')x = x * 10 + (ch & 15), ch = gt(); w ? x = ~(x - 1) : x; } template <typename T> inline void out(T x) { if(x < 0) x = -x, putchar('-'); char ch[20]; int num(0); while(x || !num) ch[++num] = x % 10 + '0', x /= 10; while(num) putchar(ch[num--]); putchar(' '); } const int MX = 1e5 + 79; int n, m; struct opt { int l, r, val; bool operator <(const opt &r)const { return this->val < r.val; } } p[MX]; int cnt, root[MX*40]; int lc[MX * 40], rc[MX * 40], sum[MX * 40], lmax[MX * 40], rmax[MX * 40]; //左儿子编号,右儿子编号,整个区间最大连续的 ,从左往右连续的,从右往左连续的 inline void pushup(int p, int L, int R) { int mid((L + R) >> 1); if(lmax[lc[p]] != (mid - L + 1)) { //左儿子左边未满 lmax[p] = lmax[lc[p]]; } else { lmax[p] = (mid - L + 1) + lmax[rc[p]]; } if(rmax[rc[p]] != (R - mid)) {//右儿子右边未满 rmax[p]=rmax[rc[p]]; } else { rmax[p]=rmax[lc[p]]+(R-mid); } sum[p]=max(max(sum[lc[p]],sum[rc[p]]),rmax[lc[p]]+lmax[rc[p]]); //左儿子连续的,右儿子连续的,两个儿子相邻的 } inline void change(int &p, int L, int R, int pos, int val) { if(!p) p = ++cnt; if(L == R) { lmax[p]=rmax[p]=sum[p]+=val; return; } int mid((L + R) >> 1); if(pos <= mid) change(lc[p], L, mid, pos, val); if(pos > mid) change(rc[p], mid + 1, R, pos, val); pushup(p, L, R); } inline void merge(int &a, int b, int L, int R) { if(!a) { a = b; return; } if(!b) return; if(L == R) { sum[a]+=sum[b]; lmax[a]+=lmax[b]; rmax[a]+= rmax[b]; return; } int mid((L + R) >> 1); merge(lc[a],lc[b] ,L, mid); merge(rc[a],rc[b], mid + 1, R); pushup(a, L, R); } /* 10 10 1 2 1 1 2 2 1 2 3 1 2 4 1 3 5 3 4 6 3 4 7 3 4 8 3 4 9 3 10 10 */ int main() { freopen("gather.in", "r", stdin); freopen("gather.out", "w", stdout); read(n); read(m); rep(i, 1, m) { read(p[i].l); read(p[i].r); read(p[i].val); } int R = 3 * MX,t(-1); sort(p + 1, p + 1 + m); p[0].val = -1; rep(i, 1, m) { if(p[i].val != p[i - 1].val) { if(p[i].val == p[i - 1].val + 1) t++; else t += 2; } change(root[p[i].l], 1, R, t, 1); change(root[p[i].r + 1], 1, R, t, -1); }//离散化 out(sum[root[1]]); rep(i, 2, n) { merge(root[1], root[i], 1, R); out(sum[root[1]]); } //每个集合里面的内容,用前缀和 表示 return 0; }