一次考试共有n个人参加，第i个人说：“有ai个人分数比我高，bi个人分数比我低。”问最少有几个人没有说真话(可能有相同的分数)
\(n \le 10^5\)
题目给的信息相当与\([a+1,n-b]\)的分数相等 于是问题转化为从一些带权区间中选出一些没有交集的区间的权值和最大
#include #include #include #include #include #include #include #include #include #include #define ls p<<1 #define rs p<<1|1 using namespace std; typedef long long ll; const int mxn=1e5+5; int n,m,cnt,hd[mxn]; inline int read() { char c=getchar(); int x=0,f=1; while(c>'9'||c<'0') {if(c=='-') f=-1;c=getchar();} while(c<='9'&&c>='0') {x=(x<<3)+(x<<1)+(c&15);c=getchar();} return x*f; } inline void chkmax(int &x,int y) {if(xy) x=y;} struct ed { int to,nxt; }t[mxn<<1]; inline void add(int u,int v) { t[++cnt]=(ed) {v,hd[u]}; hd[u]=cnt; } int tot,f[mxn]; struct T { int l,r,val; }a[mxn],b[mxn]; int cmp(T x,T y) { return x.l==y.l?x.r>1; if(a[mid].r