分析：直接差分，遇见1就+1，否则-1，那么要求的合法区间肯定是区间端点值相同。。 问题是如何计算右端点。。我一开始想二分，发现不符合二分性，然后。。然后就不会做了。。 我看其他人是直接记录？可是这种做法我一开始想过，觉得遇见极限数据肯定被卡。。我直接出一堆0，只有一个1，空间直接爆炸。。 然后我发现我是sb。。10^9是位置不是0和1的个数啊我日。。这tm不是随便算？
#include<cstdio> #include<algorithm> #include<cstring> #define fo(i,a,b) for(int i=a;i<=b;i++) #define fd(i,a,b) for(int i=a;i>=b;i--) using namespace std; int n,m; const int N=1e5+5; struct node { bool bz; int x,v; }a[N]; int f[N]; bool cmp(node a,node b) { return a.x<b.x; } int l[N],r[N]; int main() { scanf("%d",&n); fo(i,1,n) { scanf("%d%d",&a[i].bz,&a[i].x); } sort(a+1,a+1+n,cmp); int ans=0; fo(i,1,n) { if (a[i].bz)a[i].v=a[i-1].v+1; else a[i].v=a[i-1].v-1; int x=a[i].v+n; if (!l[x])l[x]=i; else r[x]=i; } fo(i,0,2*n) { if (l[i]&&r[i]) ans=max(ans,a[r[i]].x-a[l[i]+1].x); } printf("%d\n",ans); //fo(i,1,n)printf("%d %d\n",a[i].x,a[i].bz); return 0; }