题目大意
有(n)个集合，每次会将一个区间([l,r])中的所有集合加入一个数(x)。
最后询问，每个集合的最大连续段。连续段就是一个区间的元素都在一个集合中出现。
解题思路
考虑所有操作按(x)排序，所有我们只需要考虑操作的连续性即可。
对于连续性断开的区间我们区间赋(0)，否则就是区间(+1)，最后询问一个位置的历史最大值。
直接套用jls的线段树维护历史极值的操作即可。复杂度(O(nlogn))
还有一种就是按位置排序然后扫描线。
#include<cstdio>
#include<algorithm>
#define ls (x<<1)
#define rs ((x<<1)+1)
#define LL long long
using namespace std;
const int maxn=100005,INF=1e9;
inline int _read(){
int num=0;char ch=getchar();
while(ch<'0'||ch>'9') ch=getchar();
while(ch>='0'&&ch<='9') num=num*10+ch-48,ch=getchar();
return num;
}
struct jz{
int x,y;
jz(int x=0,int y=-INF):x(x),y(y){}
jz operator+(const jz &b)const{return jz(max(-INF,x+b.x),max(y+b.x,b.y));}
jz operator*(const jz &b)const{return jz(max(x,b.x),max(y,b.y));}
}tg[maxn];
struct node{
int x,l,r;
bool operator<(const node &b)const{
if (x==b.x) return l<b.l;
return x<b.x;
}
}c[maxn];
struct data{
int x1,x2;
jz add,pre;
}a[maxn*4];
int n,m,ans[maxn];
int f(int x,jz w){return max(x+w.x,w.y);}
void Pushdown(int x){
jz add=a[x].add,pre=a[x].pre;a[x].add=a[x].pre=jz();
int L=2*x,R=2*x+1;
a[L].pre=a[L].pre*(a[L].add+pre);a[L].add=a[L].add+add;
a[R].pre=a[R].pre*(a[R].add+pre);a[R].add=a[R].add+add;
a[L].x2=max(a[L].x2,f(a[L].x1,pre));a[L].x1=f(a[L].x1,add);
a[R].x2=max(a[R].x2,f(a[R].x1,pre));a[R].x1=f(a[R].x1,add);
}
void Pushup(int x){
a[x].x1=max(a[ls].x1,a[rs].x1);
a[x].x2=max(a[ls].x2,a[rs].x2);
}
void add(int x,int l,int r,int L,int R,jz w){
if (l<r) Pushdown(x);
if (l==L&&r==R){
a[x].pre=a[x].pre*(a[x].add+w);
a[x].add=a[x].add+w;
a[x].x2=max(a[x].x2,f(a[x].x1,w));a[x].x1=f(a[x].x1,w);
return;
}
int mid=l+(r-l>>1);
if (R<=mid) add(ls,l,mid,L,R,w);else
if (L>mid) add(rs,mid+1,r,L,R,w);else
add(ls,l,mid,L,mid,w),add(rs,mid+1,r,mid+1,R,w);
Pushup(x);
}
void Pushdown(int x,int l,int r){
if (l<r) Pushdown(x);
if (l==r){printf("%d ",a[x].x2);return;}
int mid=l+(r-l>>1);
Pushdown(ls,l,mid);Pushdown(rs,mid+1,r);
Pushup(x);
}
void work(){
int i=1,j,pd,now;
while(i<=m){
j=i;pd=0;now=0;while(j<=m&&c[j].x==c[i].x) j++;
if (c[i].x>c[i-1].x+1) add(1,1,n,1,n,jz(-INF,0));else pd=1;
for (int k=i;k<j;k++){
if (pd&&now+1<=c[k].l-1) add(1,1,n,now+1,c[k].l-1,jz(-INF,0));
add(1,1,n,c[k].l,c[k].r,jz(1,-INF));now=c[k].r;
}
if (pd&&now+1<=n) add(1,1,n,now+1,n,jz(-INF,0));i=j;
}
}
int main(){
freopen("exam.in","r",stdin);
freopen("exam.out","w",stdout);
n=_read();m=_read();
for (int i=1;i<=m;i++) c[i].l=_read(),c[i].r=_read(),c[i].x=_read();
sort(c+1,c+1+m);work();Pushdown(1,1,n);
return 0;
}