拟阵的一次实际运用及思考
相关题目：
P4511 [CTSC2015]日程管理
写在前面：
本题只是一道贪心题，而贪心策略也并不是很难想到。但其正确性却不是特别显然，并且贪心策略也不是能一步到位的（可能是因为本人太菜了）。
笔者发现，借助拟阵去思考这个问题的时候，其贪心策略与其正确性变得顺理成章，大大简化了思考，且使问题变得十分优雅，故写一篇博客总结。（尽管这不是本题所必要的）
当然啦本文不一定严谨，有问题欢迎指出
题意：
-
有
n 天可以用来完成任务，每天只能完成至多一个任务 -
有若干个任务，每个任务表示为
(p_i,t_i) ，意为该任务完成时间不能晚于t_i ，可获得收益为p_i 。任务可以选择不完成 -
要求支持动态增加或删除任务，以及查询当前可以获得的最大收益
-
n,Q\le3*10^5
solution：
首先介绍一个小
先把第
此题有一些明显的贪心策略，例如不带修改时可以按
记
遗传性质显然，考虑证明其交换性质：
设
由于将某个任务完成时间提前后显然更有可能合法，考虑先安排
大概长这样：
考虑
-
如果
S 中存在元素不属于A ，则显然可以将那个元素放到这个空位上 -
如果
S 中所有元素均属于A ，可以将A 中任意一个属于S 的元素拉到位置5 并递归地考虑该位置
可以发现第二种情况经过若干次递归后总能回到情况一
至此，交换性质得证，
接下来的做法就很容易想了。
首先是不带修改操作时的暴力，这相当于是求拟阵带权最大独立集，说的通俗点，就是
进一步考虑只有加入操作时怎么做。从拟阵的角度，这个问题等价于动态加边最小生成树：
先强制加入当前的边，再判断有没有成环。如果成环，就删去环上最小边。
考虑本题中环是什么，其实就是所有删去后能使任务集合合法的所有任务。
还记得开始时的那个线段树吗？我们先找到最左边的
至于删除，由于拟阵中的基大小相同，删掉一个任务后我们至多只能再加入一个任务，那就找能加入的任务中最大的。
我们可以找到当前线段树上最右的
至于怎么实现，可以用线段树套set实现查找
另外吐槽一句，开始时我没去想删除怎么做，因为删除可以以1个
总结：
从本文中可以发现，拟阵并没有给出什么独特的思路（那些贪心策略即使不知道拟阵也能想到），但却使本题系统化，并且使思考贪心策略时不用担心其正确性，对于简化思路方面起到了很大的作用，也使问题变得更加优美。可见拟阵确实为一种好的工具。
AC代码：（人傻常数大，开O2才能过，开O2能快5倍我也不知道为啥）
#include <bits/stdc++.h>
#define LL int
using namespace std;
const LL maxn=1200000+10;
const LL inf=1e9;
LL n,Q;
struct legal{
LL sp[maxn],add[maxn];
inline void up(LL id){sp[id]=min(sp[id*2],sp[id*2+1]);}
void build(LL id,LL l,LL r){
add[id]=0;
if (l==r) {sp[id]=l; return;}
LL mid=(l+r)/2;
build(id*2,l,mid); build(id*2+1,mid+1,r);
up(id);
}
void init(){ build(1,1,n);}
inline void down(LL id){
if (add[id]){
sp[id*2]+=add[id]; sp[id*2+1]+=add[id];
add[id*2]+=add[id]; add[id*2+1]+=add[id];
add[id]=0;
}
}
void updata(LL id,LL l,LL r,LL x,LL y,LL v){
if (x<=l && r<=y){
sp[id]+=v; add[id]+=v;
return;
}
down(id);
LL mid=(l+r)/2;
if (x<=mid) updata(id*2,l,mid,x,y,v);
if (y>mid) updata(id*2+1,mid+1,r,x,y,v);
up(id);
}
inline void ins(LL t){updata(1,1,n,t,n,-1);}
inline void del(LL t){updata(1,1,n,t,n,1);}
bool ok(){return sp[1]>=0;}
bool full(){return sp[1]<=0;}
LL query_l(LL id,LL l,LL r,LL mi){
if (l==r) return l;
down(id);
LL mid=(l+r)/2;
if (sp[id*2]==mi) return query_l(id*2,l,mid,mi);
else return query_l(id*2+1,mid+1,r,mi);
}
LL query_r(LL id,LL l,LL r,LL mi){
if (l==r) return l;
down(id);
LL mid=(l+r)/2;
if (sp[id*2+1]==mi) return query_r(id*2+1,mid+1,r,mi);
else return query_r(id*2,l,mid,mi);
}
inline LL lpos(){
if (sp[1]>=0) return n;
return query_l(1,1,n,sp[1]);
}
inline LL rpos(){
if (sp[1]>0) return 0;
return query_r(1,1,n,sp[1]);
}
}L;
struct Pair{
LL first,second;
bool operator<(const Pair&p) const{
return first==p.first?second<p.second:first<p.first;
}
bool operator>(const Pair&p) const{
return first==p.first?second>p.second:first>p.first;
}
bool operator==(const Pair&p) const{
return first==p.first && second==p.second;
}
};
struct dque{
priority_queue<Pair > q,dq;
inline void push(const Pair&x){
q.push(x);
}
inline void del(const Pair&x){
dq.push(x);
}
inline Pair top(){
while (!q.empty() && !dq.empty() && q.top()==dq.top()){
q.pop(); dq.pop();
}
if (q.empty()) return (Pair){-inf,0};
return q.top();
}
inline bool empty(){
while (!q.empty() && !dq.empty() && q.top()==dq.top()){
q.pop(); dq.pop();
}
return q.empty();
}
};
inline void max(Pair &x,const Pair &y){
if (y>x) x=y;
}
struct segmentree{
LL sp[maxn];
long long sum;
unordered_map<unsigned long long,LL> mp;
dque val[maxn];
segmentree(){sum=0;}
inline void up(LL id){
sp[id]=val[sp[id*2]].top()>val[sp[id*2+1]].top()?sp[id*2]:sp[id*2+1];
}
void build(LL id,LL l,LL r){
if (l==r) {sp[id]=l; return;}
LL mid=(l+r)/2;
build(id*2,l,mid); build(id*2+1,mid+1,r);
up(id);
}
void updata(LL id,LL l,LL r,LL t,LL p){
if (l==r){
val[t].push((Pair){p,t});
return;
}
LL mid=(l+r)/2;
if (t<=mid) updata(id*2,l,mid,t,p);
else updata(id*2+1,mid+1,r,t,p);
up(id);
}
void del(LL id,LL l,LL r,LL t,LL p){
if (l==r){
val[t].del((Pair){p,t});
return;
}
LL mid=(l+r)/2;
if (t<=mid) del(id*2,l,mid,t,p);
else del(id*2+1,mid+1,r,t,p);
up(id);
}
inline void ins(LL t,LL p) {updata(1,1,n,t,p); mp[12345678ull*p+t]++; sum+=p;}
inline void del(LL t,LL p){del(1,1,n,t,p);mp[12345678ull*p+t]--; sum-=p;}
inline bool exist(LL t,LL p){return mp[12345678ull*p+t];}
Pair query(LL id,LL l,LL r,LL x,LL y){
if (val[sp[id]].empty()) return (Pair){-inf,0};
if (x<=l && r<=y) return val[sp[id]].top();
LL mid=(l+r)/2; Pair ans=(Pair){-inf,0};
if (x<=mid) max(ans,query(id*2,l,mid,x,y));
if (y>mid) max(ans,query(id*2+1,mid+1,r,x,y));
return ans;
}
inline Pair qry(LL x,LL y){return query(1,1,n,x,y);}
}T1,T2;
void add(LL t,LL p){
L.ins(t); T1.ins(t,-p);
if (L.ok()) return;
LL pos=L.lpos();
Pair P=T1.qry(1,pos);
LL pp=-P.first,tt=P.second;
if (pp<-1e8) return;
T1.del(tt,-pp); T2.ins(tt,pp);
L.del(tt);
}
void del(LL t,LL p){
if (T2.exist(t,p)) {
T2.del(t,p); return;
}
T1.del(t,-p); L.del(t);
LL pos=L.rpos();
Pair P=T2.qry(pos+1,n);
LL pp=P.first,tt=P.second;
if (pp<-1e8) return;
T2.del(tt,pp); T1.ins(tt,-pp);
L.ins(tt);
}
inline LL read(){
LL x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
inline string reads(){
string res; char ch=getchar();
while (ch!=' ') res=res+ch,ch=getchar();
return res;
}
int main(){
n=read(),Q=read(); L.init();
T1.build(1,1,n); T2.build(1,1,n);
for (LL i=1;i<=Q;i++){
string op;LL x,y;
op=reads();
x=read(),y=read();
if (op[0]=='A') add(x,y);
else del(x,y);
printf("%lld\n",-T1.sum);
}
return 0;
}