Codeforces1389F.BicoloredSegments——DP+线段树，有丶东西

This way

题意&＃xff1a;

现在有n个线段&＃xff0c;每个线段有一种颜色&＃xff0c;定义一对线段是“坏的”&＃xff0c;当且仅当这对线段i,j满足以下条件&＃xff1a;
1.c[i]!&＃61;c[j]
2.i和j相交&＃xff08;包括边界&＃xff09;
问你最多能选择多少线段使得其中没有任何一对线段是坏的

题解&＃xff1a;

先后想了三种方法&＃xff0c;花了我两个半小时
接下来假设颜色为0,1
首先我得到一个结论&＃xff0c;就是c[i]只会从c[i]^1的地方转移过来。
因为如果从相同颜色的地方转移过来&＃xff0c;会有很多很烦的情况&＃xff08;或许是我菜了&＃xff09;&＃xff0c;刷掉了我前两个想法。
那么怎么找这个转移的位置&＃xff0c;可以用线段树来查询最大值。
因为我们是从相反颜色转移过来的&＃xff0c;所以这个转移的位置后面可能会有一些相同颜色的线段&＃xff0c;当然这两个要合在一起才能查询最大值。
那么我们只需要在这个做之前&＃xff0c;对c[i]^1这棵线段树的0~e[i].l-1区间&＃43;1即可。
最后还需要更新c[i]线段树的e[i].r位置。
当然这是两种更新&＃xff0c;我们需要不同处理方法&＃xff1a;

有人可能会问&＃xff0c;为什么在op&＃61;1的时候&＃xff0c;不需要加上那些&＃43;1的线段。
因为我是按右端点排序的&＃xff0c;所以&＃43;1的那些位置一定不会影响到后面的点&＃xff0c;因此不需要处理这种情况。

#include
using namespace std;
#define pa pair
const int N&＃61;6e5&＃43;5;
struct Segment_Tree{int mx[N*4],ad[N*4],f[N*4];void push_down(int root){if(!f[root])return ;mx[root<<1]&＃43;&＃61;f[root];mx[root<<1|1]&＃43;&＃61;f[root];f[root<<1]&＃43;&＃61;f[root];f[root<<1|1]&＃43;&＃61;f[root];f[root]&＃61;0;}void update(int l,int r,int root,int ql,int qr,int op,int v){if(l>&＃61;ql&&r<&＃61;qr){if(op&＃61;&＃61;1)mx[root]&＃61;max(mx[root],v);elsemx[root]&＃43;&＃61;v,f[root]&＃43;&＃61;v;return ;}push_down(root);int mid&＃61;l&＃43;r>>1;if(mid>&＃61;ql)update(l,mid,root<<1,ql,qr,op,v);if(mid<qr)update(mid&＃43;1,r,root<<1|1,ql,qr,op,v);mx[root]&＃61;max(mx[root<<1],mx[root<<1|1]);}int query(int l,int r,int root,int ql,int qr){if(l>&＃61;ql&&r<&＃61;qr)return mx[root];push_down(root);int mid&＃61;l&＃43;r>>1;int ans&＃61;0;if(mid>&＃61;ql)ans&＃61;query(l,mid,root<<1,ql,qr);if(mid<qr)ans&＃61;max(ans,query(mid&＃43;1,r,root<<1|1,ql,qr));return ans;}
}t[2];
struct edge{int l,r,c;bool operator< (const edge& a)const {return r<a.r;}
}e[N];
int a[N*2];
int main()
{int n,tot&＃61;0;scanf("%d",&n);for(int i&＃61;1;i<&＃61;n;i&＃43;&＃43;)scanf("%d%d%d",&e[i].l,&e[i].r,&e[i].c),e[i].c--,a[&＃43;&＃43;tot]&＃61;e[i].l,a[&＃43;&＃43;tot]&＃61;e[i].r;sort(a&＃43;1,a&＃43;1&＃43;tot);tot&＃61;unique(a&＃43;1,a&＃43;1&＃43;tot)-a-1;sort(e&＃43;1,e&＃43;1&＃43;n);for(int i&＃61;1;i<&＃61;n;i&＃43;&＃43;){e[i].l&＃61;lower_bound(a&＃43;1,a&＃43;1&＃43;tot,e[i].l)-a;e[i].r&＃61;lower_bound(a&＃43;1,a&＃43;1&＃43;tot,e[i].r)-a;}int ans&＃61;0,val,num[2]&＃61;{0};for(int i&＃61;1;i<&＃61;n;i&＃43;&＃43;){int col&＃61;e[i].c;num[col]&＃43;&＃43;;t[col^1].update(0,tot,1,0,e[i].l-1,2,1);val&＃61;0;val&＃61;t[col^1].query(0,tot,1,0,e[i].l-1);val&＃61;max(num[col],val);t[col].update(0,tot,1,e[i].r,e[i].r,1,val);ans&＃61;max(ans,val);}printf("%d\n",ans);return 0;
}