?
有n个操作，每个操作定义为x1,x2,c，表示把区间[x1,x2]染成c色，区间可重复染色，最后问每种颜色存在几个间断的区间中。
注意是对区间进行染色，而不是点。
成段更新很简单，在统计每种颜色所在间断的区间时，先把线段树中节点信息映射到数组中然后统计，没想到这一点，一直在想怎么在线段树上进行统计。
#include #include #include #include #include #include #include #include #include #include #include #include #include #define LL long long #define _LL __int64 #define eps 1e-12 #define PI acos(-1.0) using namespace std; const int maxn = 8010; struct node { int l,r; int col; }tree[maxn*4]; int ans[maxn]; int arr[maxn]; void build(int v, int l, int r) { tree[v].l = l; tree[v].r = r; tree[v].col = -1; if(l == r) return; int mid = (l + r) >> 1; build(v*2,l,mid); build(v*2+1,mid+1,r); } void update(int v, int l, int r, int col) { if(tree[v].l == l && tree[v].r == r) { tree[v].col = col; return; } if(tree[v].col != -1) { tree[v*2].col = tree[v*2+1].col = tree[v].col; tree[v].col = -1; } int mid = (tree[v].l + tree[v].r) >> 1; if(r <= mid) update(v*2,l,r,col); else if(l > mid) update(v*2+1,l,r,col); else { update(v*2,l,mid,col); update(v*2+1,mid+1,r,col); } } void query(int v, int l, int r) { if(tree[v].col != -1) { for(int i = tree[v].l; i <= tree[v].r; i++) { arr[i] = tree[v].col; } return; } if(tree[v].l == tree[v].r) { arr[tree[v].l] = tree[v].col; return; } int mid = (tree[v].l + tree[v].r) >> 1; if(r <= mid) query(v*2,l,r); else if(l > mid) query(v*2+1,l,r); else { query(v*2,l,mid); query(v*2+1,mid+1,r); } } int main() { int n,cn,t; int ll[maxn],rr[maxn],cc[maxn]; while(~scanf(%d,&t)) { memset(ans,0,sizeof(ans)); n = -1; cn = -1; for(int i = 1; i <= t; i++) { scanf(%d %d %d,&ll[i],&rr[i],&cc[i]); n = max(n,rr[i]); cn = max(cn,cc[i]); } build(1,0,n-1); for(int i = 1; i <= t; i++) { update(1,ll[i],rr[i]-1,cc[i]); } query(1,0,n-1); ans[arr[0]] += 1; for(int i = 1; i <= n-1; i++) { if(arr[i] != arr[i-1]) ans[arr[i]] += 1; } for(int i = 0; i <= cn; i++) { if(ans[i]) printf(%d %d ,i,ans[i]); } printf( ); } return 0; }