2024-03-29

LOG

对于小于等于 \(s\) 的数 \(x\)，最多被选 \(x\) 次
大于 \(s\) 的数最多被选 \(s\) 次

看所有小于等于 \(s\) 的数字的和加上 \(s\) 乘大于 \(s\) 的数字的个数 这个值是不是大于等于 \(c\times s\) 就行

离散化之后权值线段树维护一下

离散化之后线段树右边界应该是 nums.size()

#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>

#define ls (u<<1)
#define rs (u<<1|1)

using namespace std;

typedef long long ll;

const int N=2e6+10;

int n,m;
ll w[N];

struct Node {
	int l,r;
	ll val,cnt;
}tr[4*N];

struct Query {
	bool typ;
	ll x,y;
}qry[N];

vector<ll> nums;

ll gt(ll x) {
	return lower_bound(nums.begin(),nums.end(),x)-nums.begin();
}

void pushup(int u) {
	tr[u].val=tr[ls].val+tr[rs].val;
	tr[u].cnt=tr[ls].cnt+tr[rs].cnt;
}

void build(int u,int l,int r) {
	tr[u].l=l,tr[u].r=r;
	if(l==r) return;
	int mid=l+r>>1;
	build(ls,l,mid),build(rs,mid+1,r);
}

void update(int u,int x,int k) {
	if(tr[u].l==tr[u].r) {
		tr[u].cnt+=k;
		tr[u].val+=k*nums[x];
		return;
	}
	int mid=(tr[u].l+tr[u].r)>>1;
	if(x<=mid) update(ls,x,k);
	else update(rs,x,k);
	pushup(u);
}

Node query(int u,int l,int r) {
	if(tr[u].l>=l&&tr[u].r<=r) return tr[u];
	int mid=tr[u].l+tr[u].r>>1;
	Node res;
	res.cnt=res.val=0;
	if(l<=mid) {
		Node qrs=query(ls,l,r);
		res.cnt+=qrs.cnt,res.val+=qrs.val;
	}
	if(r>mid) {
		Node qrs=query(rs,l,r);
		res.cnt+=qrs.cnt,res.val+=qrs.val;
	}
	return res;
}

int main() {
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++) {
		char opt[3];
		scanf("%s%lld%lld",opt,&qry[i].x,&qry[i].y);
		nums.push_back(qry[i].y);
		if(*opt=='U') qry[i].typ=false;
		else qry[i].typ=true;
	}
	sort(nums.begin(),nums.end());
	nums.erase(unique(nums.begin(),nums.end()),nums.end());
	build(1,1,nums.size());
	for(int i=1;i<=m;i++) {
		ll x=qry[i].x,y=qry[i].y;
		if(!qry[i].typ) {
			if(w[x]) update(1,gt(w[x]),-1);
			w[x]=y;
			update(1,gt(w[x]),1);
		}
		else {
			if(query(1,1,gt(y)).val+y*query(1,gt(y)+1,nums.size()).cnt>=x*y) puts("TAK");
			else puts("NIE");
		}
	}
	
	return 0;
} 

考试改题

只改了一道