Luogu P4511 CTSC 2015 日程管理

正题

一开始的时候显然第\(i\)天以前可以放\(i\)个任务是吧，然后考虑用一棵线段树维护这个数量，设每天的这个值为\(lev(i)\)
考虑在\(t\)这个截止时间位置放了一个任务，那\((t,n)\)这个区间的$ lev(i)$ 都要减去\(1\)。　 　

插入

设插入的终止时间为\(t\),这个任务的价值为\(p\)。那如何插入呢？

• 当这个任务与其他的任务不冲突的时候，直接加入完事。也就是当\(min(lev(t\rightarrow n))>0\)的时候不会冲突，然后直接加进去就完事了
• 当这个任务与其他任务冲突的时候，一个显然的想法就是替换掉最小的，或者不替换。那这个最小的值在哪里找呢。为了我们可以把当前的任务加进去，那原来的这个最小值的\(t_2\)必须要比刚刚所说的\((t,n)\)的最左边的\(lev(i)=0\)的\(i\)要小才可以释放空间让当前的任务可以插入。所以就在区间 \((1,id)\) (\(id\)就是刚刚说的那个位置）找一个价值最小的任务替换掉，然后把替换掉的那个任务丢到没有用的一个集合。为什么是对的呢，因为如果不替换这个任务，那就要有一个更好的任务来替换这个任务，而这个任务比原来的要大，所以就要在中间额外插入一个任务，而显然这是做不到的，所以这个就是最优的了。　　

删除

• 显然要是没用这个任务直接删掉完事
• 其实这里你不用管就有\(20\)分了，岂不美哉？　如果用了的话，就在没有用的里面去找个最大的替换要删掉的那个任务就行了。万一找不到的话就不用管了呗。　然后剩下的自己YY一下就出来了　我这么弱都YY出来了您们肯定随便就搞出来了

至于这个集合怎么维护，显然线段树套个multiset就行了

代码

至于代码为什么这么长
当然是为了更好地装逼说明啦！　　
记得点赞啊，我就没收过赞。。。　　
下次一定的走开(bushi

#include <set>
#include <cstdio>
#include <utility>
#include <algorithm>

using namespace std;

#define R register
#define LL long long
#define IT multiset<int>::iterator

const int MAXN = 3e5 + 10;
const int inf = 1e9 + 10;

inline int read()
{
	char a = getchar();
	int x = 0, f = 1;
	for (; a > '9' || a < '0'; a = getchar())
		if (a == '-')
			f = -1;
	for (; a >= '0' && a <= '9'; a = getchar())
		x = x * 10 + a - '0';
	return x * f;
}

inline char getc()
{
	char a = getchar();
	while (a != 'A' && a != 'D')
		a = getchar();
	return a;
}

int n, m;
LL Ans;

struct Round
{
	int l, r, va;
};

class Tree_for_value
{
private:
	int tag[MAXN << 2];
	Round mn[MAXN << 2];
	inline int ls(int x);
	inline int rs(int x);
	inline void update(int x);
	inline void get(int x, int k);
	inline void pushdown(int x);

public:
	inline Round ask(int x, int l, int r, int Le, int Ri);
	inline void chg(int x, int l, int r, int Le, int Ri, int k);
	inline void build(int x, int l, int r);
} T1;

class Tree_for_mintask
{
private:
	multiset<int> st[MAXN << 2];
	pair<int, int> mn[MAXN << 2];
	inline int ls(int x);
	inline int rs(int x);
	inline void update(int x);

public:
	inline void build(int x, int l, int r);
	inline void insert(int x, int l, int r, int ad, int p);
	inline void del(int x, int l, int r, int ad, int p);
	inline pair<int, int> ask(int x, int l, int r, int Le, int Ri);
	inline int have(int x, int l, int r, int ad, int p);
} T2;

class Tree_for_maxtask
{
private:
	multiset<int> st[MAXN << 2];
	pair<int, int> mx[MAXN << 2];
	inline int ls(int x);
	inline int rs(int x);
	inline void update(int x);

public:
	inline void build(int x, int l, int r);
	inline void insert(int x, int l, int r, int ad, int p);
	inline void del(int x, int l, int r, int ad, int p);
	inline pair<int, int> ask(int x, int l, int r, int Le, int Ri);
} T3;

int main()
{
	freopen("d.in", "r", stdin);
	freopen("d.out", "w", stdout);
	n = read();
	m = read();
	T1.build(1, 1, n);
	T2.build(1, 1, n);
	T3.build(1, 1, n);
	char op;
	int t, p;
	while (m--)
	{
		op = getc();
		t = read();
		p = read();
		if (op == 'A')
		{
			Round pir = T1.ask(1, 1, n, t, n);
			if (pir.va > 0)
			{
				Ans += p;
				T1.chg(1, 1, n, t, n, -1);
				T2.insert(1, 1, n, t, p);
			}
			else
			{
				int id = pir.l;
				pair<int, int> tmp = T2.ask(1, 1, n, 1, id);
				if (tmp.first > p)
					T3.insert(1, 1, n, t, p);
				else
				{
					Ans += p - tmp.first;
					T2.del(1, 1, n, tmp.second, tmp.first);
					T3.insert(1, 1, n, tmp.second, tmp.first);
					T1.chg(1, 1, n, tmp.second, n, 1);
					T2.insert(1, 1, n, t, p);
					T1.chg(1, 1, n, t, n, -1);
				}
			}
		}
		else
		{
			if (T2.have(1, 1, n, t, p) == 0)
				T3.del(1, 1, n, t, p);
			else
			{
				Ans -= p;
				T2.del(1, 1, n, t, p);
				T1.chg(1, 1, n, t, n, 1);
				Round tmp = T1.ask(1, 1, n, 1, n);
				int id = tmp.va <= 0 ? tmp.r : 0;
				if (id != n)
				{
					pair<int, int> tmp = T3.ask(1, 1, n, id + 1, n);
					if (tmp.first != -inf)
					{
						T3.del(1, 1, n, tmp.second, tmp.first);
						T2.insert(1, 1, n, tmp.second, tmp.first);
						T1.chg(1, 1, n, tmp.second, n, -1);
						Ans += tmp.first;
					}
				}
			}
		}
		printf("%lld\n", Ans);
	}
	return 0;
}

inline int Tree_for_value::ls(int x) { return x << 1; }
inline int Tree_for_value::rs(int x) { return x << 1 | 1; }
inline void Tree_for_value::update(int x)
{
	if (mn[ls(x)].va == mn[rs(x)].va)
	{
		mn[x].va = mn[ls(x)].va;
		mn[x].l = mn[ls(x)].l;
		mn[x].r = mn[rs(x)].r;
	}
	if (mn[ls(x)].va < mn[rs(x)].va)
		mn[x] = mn[ls(x)];
	if (mn[ls(x)].va > mn[rs(x)].va)
		mn[x] = mn[rs(x)];
}
inline void Tree_for_value::get(int x, int k)
{
	tag[x] += k;
	mn[x].va += k;
}
inline void Tree_for_value::pushdown(int x)
{
	if (tag[x])
	{
		get(ls(x), tag[x]);
		get(rs(x), tag[x]);
		tag[x] = 0;
	}
}
inline void Tree_for_value::build(int x, int l, int r)
{
	if (l == r)
	{
		mn[x] = {l, l, l};
		return;
	}
	int mid = l + r;
	mid >>= 1;
	build(ls(x), l, mid);
	build(rs(x), mid + 1, r);
	update(x);
}
inline void Tree_for_value::chg(int x, int l, int r, int Le, int Ri, int k)
{
	if (l >= Le && r <= Ri)
	{
		get(x, k);
		return;
	}
	pushdown(x);
	int mid = l + r;
	mid >>= 1;
	if (Le <= mid)
		chg(ls(x), l, mid, Le, Ri, k);
	if (Ri > mid)
		chg(rs(x), mid + 1, r, Le, Ri, k);
	update(x);
}
inline Round Tree_for_value::ask(int x, int l, int r, int Le, int Ri)
{
	if (l >= Le && r <= Ri)
		return mn[x];
	pushdown(x);
	int mid = l + r;
	mid >>= 1;
	Round ans;
	if (Le > mid)
		ans = ask(rs(x), mid + 1, r, Le, Ri);
	else if (Ri <= mid)
		return ans = ask(ls(x), l, mid, Le, Ri);
	else
	{
		Round lef = ask(ls(x), l, mid, Le, Ri), rig = ask(rs(x), mid + 1, r, Le, Ri);
		if (lef.va < rig.va)
			ans = lef;
		if (lef.va > rig.va)
			ans = rig;
		if (lef.va == rig.va)
		{
			ans.l = lef.l;
			ans.r = rig.r;
			ans.va = lef.va;
		}
	}
	update(x);
	return ans;
}

inline int Tree_for_mintask::ls(int x) { return x << 1; }
inline int Tree_for_mintask::rs(int x) { return x << 1 | 1; }
inline void Tree_for_mintask::update(int x)
{
	if (mn[ls(x)].first <= mn[rs(x)].first)
		mn[x] = mn[ls(x)];
	else
		mn[x] = mn[rs(x)];
}
inline void Tree_for_mintask::build(int x, int l, int r)
{
	if (l == r)
	{
		mn[x] = make_pair(inf, l);
		return;
	}
	int mid = l + r;
	mid >>= 1;
	build(ls(x), l, mid);
	build(rs(x), mid + 1, r);
	update(x);
}
inline void Tree_for_mintask::insert(int x, int l, int r, int ad, int p)
{
	if (l == r)
	{
		st[x].insert(p);
		mn[x].first = min(mn[x].first, p);
		return;
	}
	int mid = l + r;
	mid >>= 1;
	if (ad <= mid)
		insert(ls(x), l, mid, ad, p);
	else
		insert(rs(x), mid + 1, r, ad, p);
	update(x);
}
inline void Tree_for_mintask::del(int x, int l, int r, int ad, int p)
{
	if (l == r)
	{
		st[x].erase(st[x].find(p));
		if (st[x].size())
			mn[x].first = *st[x].begin();
		else
			mn[x].first = inf;
		return;
	}
	int mid = l + r;
	mid >>= 1;
	if (ad <= mid)
		del(ls(x), l, mid, ad, p);
	if (ad > mid)
		del(rs(x), mid + 1, r, ad, p);
	update(x);
}
inline pair<int, int> Tree_for_mintask::ask(int x, int l, int r, int Le, int Ri)
{
	if (l >= Le && r <= Ri)
		return mn[x];
	int mid = l + r;
	mid >>= 1;
	if (Le > mid)
		return ask(rs(x), mid + 1, r, Le, Ri);
	if (Ri <= mid)
		return ask(ls(x), l, mid, Le, Ri);
	pair<int, int> lef = ask(ls(x), l, mid, Le, Ri), rig = ask(rs(x), mid + 1, r, Le, Ri);
	if (lef.first <= rig.first)
		return lef;
	return rig;
}
inline int Tree_for_mintask::have(int x, int l, int r, int ad, int p)
{
	if (l == r)
		return st[x].find(p) != st[x].end();
	int mid = l + r;
	mid >>= 1;
	if (ad <= mid)
		return have(ls(x), l, mid, ad, p);
	else
		return have(rs(x), mid + 1, r, ad, p);
}

inline int Tree_for_maxtask::ls(int x) { return x << 1; }
inline int Tree_for_maxtask::rs(int x) { return x << 1 | 1; }
inline void Tree_for_maxtask::update(int x)
{
	if (mx[ls(x)].first > mx[rs(x)].first)
		mx[x] = mx[ls(x)];
	else
		mx[x] = mx[rs(x)];
}
inline void Tree_for_maxtask::build(int x, int l, int r)
{
	if (l == r)
	{
		mx[x] = make_pair(-inf, l);
		return;
	}
	int mid = l + r;
	mid >>= 1;
	build(ls(x), l, mid);
	build(rs(x), mid + 1, r);
	update(x);
}
inline void Tree_for_maxtask::insert(int x, int l, int r, int ad, int p)
{
	if (l == r)
	{
		st[x].insert(p);
		mx[x].first = max(mx[x].first, p);
		return;
	}
	int mid = l + r;
	mid >>= 1;
	if (ad <= mid)
		insert(ls(x), l, mid, ad, p);
	else
		insert(rs(x), mid + 1, r, ad, p);
	update(x);
}
inline void Tree_for_maxtask::del(int x, int l, int r, int ad, int p)
{
	if (l == r)
	{
		st[x].erase(st[x].find(p));
		if (st[x].size())
		{
			IT it = st[x].end();
			it--;
			mx[x].first = *it;
		}
		else
			mx[x].first = -inf;
		return;
	}
	int mid = l + r;
	mid >>= 1;
	if (ad <= mid)
		del(ls(x), l, mid, ad, p);
	if (ad > mid)
		del(rs(x), mid + 1, r, ad, p);
	update(x);
}
inline pair<int, int> Tree_for_maxtask::ask(int x, int l, int r, int Le, int Ri)
{
	if (l >= Le && r <= Ri)
		return mx[x];
	int mid = l + r;
	mid >>= 1;
	if (Le > mid)
		return ask(rs(x), mid + 1, r, Le, Ri);
	if (Ri <= mid)
		return ask(ls(x), l, mid, Le, Ri);
	pair<int, int> lef = ask(ls(x), l, mid, Le, Ri), rig = ask(rs(x), mid + 1, r, Le, Ri);
	if (lef.first > rig.first)
		return lef;
	return rig;
}