Codeforces 702F T-Shirts 題解

Codeforces 702F T-Shirts

題目

https://codeforces.com/contest/702/problem/F

有$N$個商品，每個商品都有他的質量與價格，接下來有$M$個顧客，第$i$個顧客的預算為$a_i$，且每個顧客的購買策略都是：優先買質量最高的商品，如果質量都相同的話就選價格低的優先，且每個商品都限買一次。

每個客人購買商品都是獨立的事件，請問每個客人最多能買到幾個商品。

Solution

我們可以先把商品依照質量和價格按照購買策略排序，先從質量由大排到小，如果質量一樣就由價錢小排到大，然後每個客人都當作是一筆詢問，而我們可以依照排序好的商品去更新每個詢問的答案，假設目前商品價格是$C$，那我們就把詢問中$\ge C$的值給扣掉$C$，然後詢問的答案就$+1$，代表買了這個商品。

那這樣如果暴力做的話時間複雜度會是爛掉的$O(NM)$，所以我們可以想辦法優化他，首先，我們可以將詢問由小排到大，這樣找第一個大於等於$C$的值的位置到最後一個值的位置都要$-C$，然後他們的答案要$+1$，這裡會需要支援區間修改單點查詢的資料結構，Treap、BIT、Segment Tree都可以做到，且時間複雜度是好好的$O(logN)$。

可是，修改完之後，詢問的序列似乎就沒有排序好了，所以後面的更新就沒辦法用一樣的方式去做，那我們該怎麼解決序列修改完後沒辦法排序好的問題呢？我們可以按照原本詢問序列的值分成三個區間，$[0,C)、[C,2C),[2C,\infty)$，而第三個區間的詢問都修改完後順序是不會被影響的，唯一會被影響的就是第二個區間和第一個區間，因為第二個區間修改完後會和第一個區間合併，導致順序被更動，所以，我們可以暴力的去合併前兩個區間，然後第三個區間就只要做區間修改，打上懶人標記就行了，因為要合併前兩個區間，所以剛剛說的資料結構就只剩下Treap可以支援這個操作了，那為什麼這樣的時間複雜度會是好的呢？我們可以觀察到，會進行暴力合併的只有落在第二個區間裡面的數字，需要按照值的大小插入第一個區間內，這樣才能維護由小到大的順序，而落在第二個區間內的數字經過修改後會被減掉一半以上，所以一個數字最多只能減掉$\log_2(A)$次，$A$是值域大小，總時間複雜度是$O(N\log(N)\log(A))$。

AC Code

#include <bits/extc++.h>
#include <bits/stdc++.h>
#pragma gcc optimize("ofast, unroll-loops, no-stack-protector, fast-math")
#pragma gcc target("abm, bmi, bmi2, mmx, sse, sse2, sse3, ssse3, sse4, popcnt, avx, avx2, fma, tune=native")
#pragma comment(linker, "/stack:200000000")
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define int long long
#define double long double
#define pb push_back
#define sz(x) (int)(x).size()
#define all(v) begin(v),end(v)
#define debug(x) cerr<<#x<<" = "<<x<<'\n'
#define LINE cout<<"\n-----------------\n"
#define endl '\n'
#define VI vector<int>
#define F first
#define S second
#define MP(a,b) make_pair(a,b)
#define rep(i,m,n) for(int i = m;i<=n;++i)
#define res(i,m,n) for(int i = m;i>=n;--i)
#define gcd(a,b) __gcd(a,b)
#define lcm(a,b) a*b/gcd(a,b)
#define Case() int _;cin>>_;for(int Case = 1;Case<=_;++Case)
#define pii pair<int,int>
using namespace __gnu_cxx;
using namespace __gnu_pbds;
using namespace std;
template <typename K, typename cmp = less<K>, typename T = thin_heap_tag> using _heap = __gnu_pbds::priority_queue<K, cmp, T>;
template <typename K, typename M = null_type> using _hash = gp_hash_table<K, M>;
const int N = 1e6+5,L = 20,mod = 998244353,inf = 5e15+5;
const double eps = 1e-7;
mt19937 mt(hash<string>()("Treap"));
template<class T>struct Treap{
	struct node{
		node *l = NULL,*r = NULL;
		T key,ans = 0,add = 0,add_ans = 0,id;
		int pri = mt(),sz = 1;
		node(T x,int i):key(x),id(i){}
		~node(){
			for(auto &i:{l,r})
				delete i;
		}
		void push(){
			if(!add and !add_ans)return;
			key+=add,ans+=add_ans;
			for(auto &i:{l,r})
				if(i)i->add+=add,i->add_ans+=add_ans;
			add = 0,add_ans = 0;
		}
		void pull(){
			sz = 1;
			for(auto i:{l,r})
				if(i)sz+=i->sz;
		}
		void dfs(vector<int>&v){
			push();
			if(l)l->dfs(v);
			v[id] = ans;
			if(r)r->dfs(v);
		}
	};
	node *root = NULL;
	int size(node *a){
		return a?a->sz:0;
	}
	node *merge(node *a,node *b){
		if(!a or !b)return a?:b;
		if(a->pri>b->pri){
			a->push();
			a->r = merge(a->r,b);
			a->pull();
			return a;
		}
		else{
			b->push();
			b->l = merge(a,b->l);
			b->pull();
			return b;
		}
	}
	void split(node *t,int k,node *&a,node *&b){
		if(!t){a = b = NULL;return;}
		t->push();
		if(size(t->l)+1<=k){
			a = t;
			split(t->r,k-size(t->l)-1,a->r,b);
			a->pull();
		}
		else{
			b = t;
			split(t->l,k,a,b->l);
			b->pull();
		}
	}
	void split_by_key(node *t,int k,node *&a,node *&b){
		if(!t){a = b = NULL;return;}
		t->push();
		if(t->key<=k){
			a = t;
			split_by_key(t->r,k,a->r,b);
			a->pull();
		}
		else{
			b = t;
			split_by_key(t->l,k,a,b->l);
			b->pull();
		}
	}
	void insert(node *&t,node *c){
		node *a,*b;
		split_by_key(t,c->key,a,b);
		t = merge(a,merge(c,b));
	}
	void insert(T x,int id){
		insert(root,new node(x,id));
	}
	node *merge2(node *a,node *b){
		if(!a or !b)return a?:b;
		a->push();
		b->push();
		a = merge2(a,b->l);
		a = merge2(a,b->r);
		b->l = b->r = NULL;
		insert(a,b);
		return a;
	}
	void update(T k){
		node *a,*b,*c;
		split_by_key(root,k-1,a,b);
		if(b==NULL)return;
		b->add+=-k,b->add_ans++;
		split_by_key(b,k-1,b,c);
		root = merge(merge2(a,b),c);
	}
};
void solve(){
	int n;cin>>n;
	vector<pii>item(n);
	for(int i = 0;i<n;++i){
		cin>>item[i].F>>item[i].S;
	}
	sort(all(item),[&](pii a,pii b){
		if(a.S!=b.S)return a.S>b.S;
		return a.F<b.F;
	});
	int q;cin>>q;
	vector<pii>qry(q);
	VI ans(q);
	for(int i = 0;i<q;++i){
		cin>>qry[i].F;
		qry[i].S = i;
	}
	sort(all(qry));
	Treap<int>tp;
	for(int i = 0;i<q;++i){
		tp.insert(qry[i].F,qry[i].S);
	}
	for(int i = 0;i<n;++i){
		int x = item[i].F;
		tp.update(x);
	}
	tp.root->dfs(ans);
	for(int i = 0;i<q;++i){
		cout<<ans[i]<<' ';
	}
	cout<<endl;
}
signed main(){
	IOS;
	//Case()
	solve();
}