本文主要是介绍CF377D Developing Game [扫描线]，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
传送门
挺好的一道题...
我们考虑每一个点对哪一些答案有贡献
那么就是左端点在li-xi的区间, 右端点在xi-ri的区间有贡献
放到二维平面上, 就是一个矩形, 扫描线看什么时候最大就可以了
#include<bits/stdc++.h>
#define N 300050
using namespace std;
int read(){int cnt = 0; char ch = 0;while(!isdigit(ch)) ch = getchar();while(isdigit(ch)) cnt = cnt*10 + (ch-'0'), ch = getchar();return cnt;
}
struct Node{int x,l,r,val;friend bool operator < (const Node &a,const Node &b){return a.x == b.x ? a.val < b.val : a.x < b.x;}
}a[N]; int tot;
struct Pos{int l,x,r;}p[N];
struct Segmentree{ int Pos,val,tag;}t[N<<2];
int n,ans,L,R;
void Pushup(int x){ if(t[x<<1].val > t[x<<1|1].val){t[x].val = t[x<<1].val;t[x].Pos = t[x<<1].Pos;}else{t[x].val = t[x<<1|1].val;t[x].Pos = t[x<<1|1].Pos;}
}
void Pushdown(int x){if(t[x].tag){t[x<<1].val += t[x].tag; t[x<<1].tag += t[x].tag;t[x<<1|1].val += t[x].tag; t[x<<1|1].tag += t[x].tag;t[x].tag = 0;}
}
void Build(int x,int l,int r){if(l==r){ t[x].Pos = l; return;}int mid = (l+r) >> 1; Build(x<<1,l,mid); Build(x<<1|1,mid+1,r);Pushup(x);
}
void Modify(int x,int l,int r,int L,int R,int v){if(L<=l && r<=R){ t[x].val += v, t[x].tag += v; return;}Pushdown(x); int mid = (l+r) >> 1;if(L<=mid) Modify(x<<1, l, mid, L, R, v);if(R>mid) Modify(x<<1|1, mid+1, r, L, R, v);Pushup(x);
}
int main(){n = read(); Build(1,1,N-50);for(int i=1;i<=n;i++){int l = read(), x = read(), r = read();a[++tot] = (Node){l, x, r, 1};a[++tot] = (Node){x+1, x, r, -1};p[i] = (Pos){l,x,r};} sort(a+1, a+tot+1);for(int i=1;i<=tot;i++){Modify(1,1,N-50, a[i].l, a[i].r, a[i].val);if(t[1].val > ans){ans = t[1].val; L = a[i].x; R = t[1].Pos;}} printf("%d\n",ans); for(int i=1;i<=n;i++)if(p[i].x >= L && p[i].x <= R && p[i].l<=L && p[i].r>=R)printf("%d ",i);return 0;
}
这篇关于CF377D Developing Game [扫描线]的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
