在哪个网站做一照一码,硬件开发工程师面试问题,成都装修公司哪家实惠,哈尔滨市人社app对于一个所选任务集合#xff0c;如果对于任意时刻$i$#xff0c;$i$前面所选任务数都不超过i的话#xff0c;那么这些任务可以全选。 维护一棵线段树$T$#xff0c;第$i$个位置一开始为$i$#xff0c;每使用一个任务#xff0c;$[t,T]$都要减$1$。 插入一个任务#xf…对于一个所选任务集合如果对于任意时刻$i$$i$前面所选任务数都不超过i的话那么这些任务可以全选。 维护一棵线段树$T$第$i$个位置一开始为$i$每使用一个任务$[t,T]$都要减$1$。 插入一个任务 首先查询$[t,T]$的区间内第一个$0$的位置记为$k$。 如果没有$0$那么可以直接加入这个任务。 否则要么不用这个任务要么拿这个任务去替换$t$在$[1,k]$里价值最小的任务。 删除一个任务 如果没有使用那么直接删除。 否则$[t,T]$都要加$1$然后找到最后一个$0$的位置$k$。 那么要在备用任务集合中取出$t$在$[k1,T]$里价值最大的任务加入答案。 于是再按$t$用两棵线段树分别维护两个集合即可。 时间复杂度$O(Q\log T)$。 #includecstdio
#includeset
#includemap
#includealgorithm
using namespace std;
typedef pairint,intP;
const int N300010,M1050000;
int n,m,x,y,z,g[N],nxt[N],ed,cnt;char ch;long long ans;mapP,intid;
struct E{int t,p,u;E(){}E(int _t,int _p){t_t,p_p,u0;}}e[N];
inline int getid(int x,int y){int tid[P(x,y)],pg[t];g[t]nxt[g[t]];return p;
}
inline void read(inta){char c;while(!(((cgetchar())0)(c9)));ac-0;while(((cgetchar())0)(c9))(a*10)c-0;}
int v[M],tag[M];
inline void add1(int x,int p){v[x]p,tag[x]p;}
inline void pb(int x){if(tag[x])add1(x1,tag[x]),add1(x1|1,tag[x]),tag[x]0;}
inline void up(int x){v[x]min(v[x1],v[x1|1]);}
void build(int x,int a,int b){v[x]a;if(ab)return;int mid(ab)1;build(x1,a,mid),build(x1|1,mid1,b);
}
void add(int x,int a,int b,int c,int d,int p){if(cabd){add1(x,p);return;}pb(x);int mid(ab)1;if(cmid)add(x1,a,mid,c,d,p);if(dmid)add(x1|1,mid1,b,c,d,p);up(x);
}
int left(int x,int a,int b,int c,int d){if(v[x])return 0;if(ab)return a;pb(x);int mid(ab)1,t0;if(cmid)tleft(x1,a,mid,c,d);if(!tdmid)tleft(x1|1,mid1,b,c,d);up(x);return t;
}
int right(int x,int a,int b,int c,int d){if(v[x])return 0;if(ab)return a;pb(x);int mid(ab)1,t0;if(dmid)tright(x1|1,mid1,b,c,d);if(!tcmid)tright(x1,a,mid,c,d);up(x);return t;
}
struct SegmentTree{
setPA[N];int cnt[N],mi[M],ma[M];
inline int umax(int a,int b){if(!a)return b;if(!b)return a;return e[a].pe[b].p?a:b;
}
inline int umin(int a,int b){if(!a)return b;if(!b)return a;return e[a].pe[b].p?a:b;
}
void add(int x,int a,int b,int c,int p){if(ab){cnt[a];A[a].insert(P(e[p].p,p));mi[x]A[a].begin()-second;ma[x]A[a].rbegin()-second;return;}int mid(ab)1;if(cmid)add(x1,a,mid,c,p);else add(x1|1,mid1,b,c,p);mi[x]umin(mi[x1],mi[x1|1]);ma[x]umax(ma[x1],ma[x1|1]);
}
void del(int x,int a,int b,int c,int p){if(ab){cnt[a]--;A[a].erase(P(e[p].p,p));if(cnt[a]){mi[x]A[a].begin()-second;ma[x]A[a].rbegin()-second;}else mi[x]ma[x]0;return;}int mid(ab)1;if(cmid)del(x1,a,mid,c,p);else del(x1|1,mid1,b,c,p);mi[x]umin(mi[x1],mi[x1|1]);ma[x]umax(ma[x1],ma[x1|1]);
}
int askmin(int x,int a,int b,int c,int d){if(cabd)return mi[x];int mid(ab)1,t0;if(cmid)taskmin(x1,a,mid,c,d);if(dmid)tumin(t,askmin(x1|1,mid1,b,c,d));return t;
}
int askmax(int x,int a,int b,int c,int d){if(cabd)return ma[x];int mid(ab)1,t0;if(cmid)taskmax(x1,a,mid,c,d);if(dmid)tumax(t,askmax(x1|1,mid1,b,c,d));return t;
}
}T1,T2;
inline void addtask(int x){int te[x].t,kleft(1,1,n,t,n);if(!k){add(1,1,n,t,n,-1);T1.add(1,1,n,t,x);e[x].u1;anse[x].p;}else{int yT1.askmin(1,1,n,1,k);if(e[y].pe[x].p){add(1,1,n,e[y].t,n,1);T1.del(1,1,n,e[y].t,y);T2.add(1,1,n,e[y].t,y);e[y].u0;add(1,1,n,t,n,-1);T1.add(1,1,n,t,x);e[x].u1;anse[x].p-e[y].p;}else T2.add(1,1,n,t,x);}
}
inline void deltask(int x){if(!e[x].u)T2.del(1,1,n,e[x].t,x);else{ans-e[x].p;add(1,1,n,e[x].t,n,1);T1.del(1,1,n,e[x].t,x);int kright(1,1,n,1,n),yT2.askmax(1,1,n,k1,n);if(y){add(1,1,n,e[y].t,n,-1);T2.del(1,1,n,e[y].t,y);T1.add(1,1,n,e[y].t,y);e[y].u1;anse[y].p;}}
}
int main(){read(n),read(m),build(1,1,n);while(m--){while((chgetchar())!Ach!D);read(x),read(y);if(chA){e[ed]E(x,y);if(!id[P(x,y)])zid[P(x,y)]cnt;else zid[P(x,y)];nxt[ed]g[z],g[z]ed;addtask(ed);}else deltask(getid(x,y));printf(%lld\n,ans);}return 0;
}转载于:https://www.cnblogs.com/clrs97/p/5170412.html
