Ural 1019 Line Painting 速递：https://acm.timus.ru/problem.aspx?space=1&num=1019 N次给线[0,1e9]填色，初始整条线是白的，每次将一个段 [ l，r ] 填成黑或白。 问最长段的左右端点。
做法是离散化后直接暴力。
样例： 4 1 999999997 b 40 300 w 300 634 w 43 47 b 涂色应该是 [ x , y ) 如此答案中数字必来自原输入。
#include<cstdio> #include<iostream> #include<algorithm> #include<string> #include<cstring> #include<cmath> #include<vector> #include<map> #include<queue> using namespace std; const int maxn=1e6+6; char s[5]; struct Node{ int l,r,c; }nt[maxn],seg[maxn]; vector<int>vc; map<int,int>mp; int main(){ int N; cin>>N; for(int i=0;i<N;i++){ int l,r; scanf("%d%d%s",&l,&r,s); int c=0; if(s[0]=='b')c=1; nt[i]=(Node){l,r,c}; vc.push_back(l); vc.push_back(r); } vc.push_back(0); vc.push_back(1000000000); sort(vc.begin(),vc.end()); int cnt=unique(vc.begin(),vc.end())-vc.begin(); int poi=1; for(int i=0;i<cnt;i++){ int x=vc[i]; seg[poi].l=seg[poi].r=x; seg[poi].c=0; mp[x]=poi; poi++; } for(int i=0;i<N;i++){ int l,r,c; l=nt[i].l; r=nt[i].r; c=nt[i].c; for(int j=mp[l];j<mp[r];j++) seg[j].c=c; } int s=-1; int ans=-1; int ml,mr; ml=mr=0; for(int i=1;i<poi;i++){ if(s==-1&&seg[i].c==0)s=seg[i].l; if(seg[i].c==1&&s!=-1){ if(ans<(seg[i].l-s)){ ans=seg[i].l-s; ml=s; mr=seg[i].l; } s=-1; } } if(seg[poi-1].c==0){ if(ans<seg[poi-1].l-s){ ans=seg[poi-1].l-s; ml=s; mr=seg[poi-1].l; } } printf("%d %d\n",ml,mr); }