题意，给你n个 x,y,c，意思就是区间[x,y]被染成C色，但是颜色会被覆盖的，染色操作完成以后 问你每种颜色有多少段 并输出颜色编号id跟段数cnt
经典问题，不过写的有点撮吧，没去看别人的，这个方法应该是最传统的最普通的，常规的开数组记录，也许大神们有更高端的方法
#include #include #include #include #include #include #include #include #include #include #include #include #include #include #define ll long long #define LL __int64 #define eps 1e-8 #define inf 0xfffffff //const LL INF = 1LL<<61; using namespace std; //vector > G; //typedef pair P; //vector > ::iterator iter; // //map mp; //map ::iterator p; const int N = 8000 + 5; typedef struct Node { int l,r; int col; }; Node tree[N * 4]; int color[N]; int ans[N]; void init() { memset(color,-1,sizeof(color)); memset(ans,0,sizeof(ans)); } void build(int l,int r,int id) { tree[id].l = l; tree[id].r = r; tree[id].col = -1; if(l == r)return; int mid = (l + r)/2; build(l,mid,id<<1); build(mid+1,r,id<<1|1); } void cal(int id) { if(tree[id].col > -1) { tree[id<<1].col = tree[id].col; tree[id<<1|1].col = tree[id].col; tree[id].col = -1; } } void update(int l,int r,int id,int col) { if(tree[id].col == col)return; if(l <= tree[id].l && r >= tree[id].r) { tree[id].col = col;return; } cal(id); int mid = (tree[id].l + tree[id].r)/2; if(r <= mid)update(l,r,id<<1,col); else if(l > mid)update(l,r,id<<1|1,col); else { update(l,mid,id<<1,col); update(mid+1,r,id<<1|1,col); } } void query(int l,int r,int id) { if(tree[id].col > -1) { for(int i=tree[id].l;i<=tree[id].r;i++) color[i] = tree[id].col; return; } if(tree[id].l == tree[id].r)return; int mid = (tree[id].l + tree[id].r)/2; if(r <= mid)query(l,r,id<<1); else if(l > mid)query(l,r,id<<1|1); else { query(l,mid,id<<1); query(mid+1,r,id<<1|1); } } int main() { int n; while(scanf("%d",&n) == 1) { int q = n; init(); build(1,N,1); int x,y,c; while(q--) { scanf("%d %d %d",&x,&y,&c); x++; update(x,y,1,c); } query(1,N,1); for(int i=1;i -1) ans[color[i]]++; for(int i=0;i