前言
好题啊，这很NOIP。
题目
模拟赛的题，我就不放出(搬)题人的fAKe题面了，可以去 CF 看原题。
题目大意：
( t LLL) 对假期里同学们的表现不是很满意，于是她决定来 (N) 次突击检查，每次她会挑选 (a_i) 个同学(显然是不同的)到她的办公室，然而同学们的忍耐程度是有极限的，对于这 (M) 个同学来说，每个人有一个忍耐程度 (b_i)，表示他/她最多能忍受被 ( t LLL) 叫去办公室的次数，一旦到达极限，他/她将逃离教室，同学们在没有达到极限的时候会尽可能满足 ( t LLL) 的要求。
但随着时间的推移，( t LLL) 的抽查和同学们的程度都会有所变化。
具体的，共有 (Q) 个时间点，每个时间点到达后会有以下四种变化情况：
- (1 i) ：(a_i) 加一。
- (2 i) ：(a_i) 减一。
- (3 j) ：(b_j) 加一。
- (4 j) ：(b_j) 减一。
对于每个时间点，你需要回答同学们是否能够满足 ( t LLL) 的抽查要求。
(1le N,M,Qle 250000;0le a_i,b_ile 250000.)
数据保证任意时刻 (a,b) 非负。
讲解
首先试图用一个式子来表示合法时的情况：
对 (a) 从大到小排序后，当且仅当 (forall kin[1,N],sum_{i=1}^k a_ile sum_{i=1}^Mmin(b_i,k))。
具体证明可以去看 _Wallace_巨佬 的博客。
我们对每个 (k) 维护 (sum_{i=1}^Mmin(b_i,k)-sum_{i=1}^ka_i)，但是直接做不好做，考虑转换。
令 (c_k=sum_{i=1}^M[b_ige k])，则上面的式子可以化为 (sum_{i=1}^k(c_i-a_i))，是一个很舒服的式子，用线段树很好维护。
- 对于 (a) 的改动，由于每次只改 (1)，所以二分出最前面/后面那个点直接改就好，单调不降性质依然保持。
- 对于 (b) 的改动，显然只会对 (1) 个 (c) 有影响，可以直接改。
时间复杂度 (O(nlog_2n))。
代码
普通线段树
//12252024832524
#include <cstdio>
#include <cstring>
#include <algorithm>
#define TT template<typename T>
using namespace std;
typedef long long LL;
const int MAXN = 250005;
const LL INF = 1ll << 60;
int n,m;
int a[MAXN],b[MAXN],nowa[MAXN];
LL cha[MAXN];
LL Read()
{
LL x = 0,f = 1; char c = getchar();
while(c > '9' || c < '0'){if(c == '-') f = -1;c = getchar();}
while(c >= '0' && c <= '9'){x = (x*10) + (c^48);c = getchar();}
return x * f;
}
TT void Put1(T x)
{
if(x > 9) Put1(x/10);
putchar(x%10^48);
}
TT void Put(T x,char c = -1)
{
if(x < 0) putchar('-'),x = -x;
Put1(x); if(c >= 0) putchar(c);
}
TT T Max(T x,T y){return x > y ? x : y;}
TT T Min(T x,T y){return x < y ? x : y;}
TT T Min(T x){return x < 0 ? -x : x;}
#define lc (x<<1)
#define rc (x<<1|1)
LL MIN[MAXN << 2],lz[MAXN << 2];
void calc(int x,int val){MIN[x] += val; lz[x] += val;}
void up(int x){MIN[x] = Min(MIN[lc],MIN[rc]);}
void down(int x){if(!lz[x]) return; calc(lc,lz[x]); calc(rc,lz[x]); lz[x] = 0;}
void Add(int x,int l,int r,int ql,int qr,int val)
{
if(ql > qr) return;
if(ql <= l && r <= qr)
{
calc(x,val);
return;
}
int mid = (l+r) >> 1;
down(x);
if(ql <= mid) Add(lc,l,mid,ql,qr,val);
if(mid+1 <= qr) Add(rc,mid+1,r,ql,qr,val);
up(x);
}
int main()
{
// freopen("problem.in","r",stdin);
// freopen("problem.out","w",stdout);
n = Read(); m = Read();
for(int i = 1;i <= n;++ i) nowa[i] = a[i] = Read();
for(int i = 1;i <= m;++ i) b[i] = Read(),--cha[b[i]+1],++cha[1];
sort(nowa+1,nowa+n+1,[](int x,int y){return x > y;});
for(int i = 1;i <= n;++ i) Add(1,1,n,i,n,-nowa[i]);
for(int i = 1;i <= n;++ i) cha[i] += cha[i-1],Add(1,1,n,i,n,cha[i]);
for(int Q = Read(); Q ;-- Q)
{
int opt = Read(),pos = Read();
if(opt == 1)
{
int v = a[pos]; ++a[pos];
int l = 1,r = n,ret = 1;
while(l <= r)
{
int mid = (l+r) >> 1;
if(nowa[mid] <= v) r = mid-1,ret = mid;
else l = mid+1;
}
Add(1,1,n,ret,n,-1);
++nowa[ret];
}
else if(opt == 2)
{
int v = a[pos]; --a[pos];
int l = 1,r = n,ret = 1;
while(l <= r)
{
int mid = (l+r) >> 1;
if(nowa[mid] >= v) l = mid+1,ret = mid;
else r = mid-1;
}
Add(1,1,n,ret,n,1);
--nowa[ret];
}
else if(opt == 3)
{
++b[pos];
Add(1,1,n,b[pos],n,1);
}
else
{
Add(1,1,n,b[pos],n,-1);
--b[pos];
}
if(MIN[1] >= 0) Put(1,'
');
else Put(0,'
');
}
return 0;
}
后记
这题只用了简单的线段树，却涉及到了网络流的知识，可以说是非常NOIP了。