[NOIP2015模拟10.27] [JZOJ4270] 魔道研究 解题报告(动态开点+权值线段树上二分)
题目大意：给定t个集合，我们要维护任意区间加入和删除元素，并且把第q区间前q大的元素放在一起维护一个新的集合的前n大
“我们有若干个可重集合，然后我们从第 i 个可重集合中拿前 i 大组成一个新的可重集合 S。我们的目的是动态维护 S 的前 n 大的和。–来自题解
好的，集合第k大的感觉，一开始怀疑是主席树，但是并不是
题解：
显然，我们需要维护所有的小集合以及 S。 维护 maxt 棵权值线段树，第 i 棵线段树对应第 i 个小集合。 我们称这些线段树为小树。 另外维护一棵权值线段树，用来维护 S。我们称这棵线段树为大树。对于 BORROW 操作，我们就是在第 t 棵小树中加入一个元素 p。这个可以通过线段树单点修改完成。 之后，我们要确定要不要将 p 加入 S 中。这个只要知道 p 在第 t 个集合中的排名是否 ≤ t 即可。 加入了 S 以后，我们还要将原来的第 t 大，即现在的第 t+1 大从 S 中删去。对于 RETURN 操作，我们可以类似地，将 BORROW 操作取反即可。而动态维护S前n大的和自然也是小菜一碟了。
需要注意的细节：
①我们区间查找的始终是从大到小的，因此我们在权值线段树上二分的时候要先比较右节点
②val数组维护的是和，而权值在叶子节点上
③权值线段树的空间需求是不能接受的，但动态开点可以解决这个问题
④不要用cin读入字符串，笔者在这儿足足卡了一个小时TLE
⑤S的根节点不能叫n+1，这是一个坑，题目没有说是我浪了，一直20分
官方题解：https://jzoj.net/senior/index.php/main/download/4270/slide.pdf/0/solution_path，不知道能不能打开
#include<iostream> #include<cstdio> #include<algorithm> #define ll long long using namespace std; const int maxn=300010; const int Y=1000000050; int n,m,sz,tr; ll val[maxn*90]; int tree[maxn],sum[maxn*90]; char c[20]; struct TREE { int l;int r; }t[maxn*90]; inline int read() { char ch=getchar(); int s=0,f=1; while (!(ch>='0'&&ch<='9')) {if (ch=='-') f=-1;ch=getchar();} while (ch>='0'&&ch<='9') {s=(s<<3)+(s<<1)+ch-'0';ch=getchar();} return s*f; } void update(int &rt,int l,int r,int pos,int z) { if (!rt) rt=++sz; if (!pos) return; if (l==r) { sum[rt]+=z; val[rt]=sum[rt]*l; return; } int mid=l+r>>1; if (pos<=mid) update(t[rt].l,l,mid,pos,z); else update(t[rt].r,mid+1,r,pos,z); sum[rt]=sum[t[rt].l]+sum[t[rt].r]; val[rt]=val[t[rt].l]+val[t[rt].r]; return; } ll query(int &rt,int l,int r,int ls,int rs) { if (!rt) {rt=++sz;return 0;} if (l>=ls&&r<=rs) return sum[rt]; int mid=l+r>>1; int qq=0; if (ls<=mid) qq+=query(t[rt].l,l,mid,ls,rs); if (rs>mid) qq+=query(t[rt].r,mid+1,r,ls,rs); return qq; } int get1(int &rt,int l,int r,int xth)//从大到小第xth个数是多少 pos { if (!rt) rt=++sz; if (!xth) return 0; if (xth>sum[rt]) return 0; if (l==r) return l; int mid=l+r>>1; if (xth<=sum[t[rt].r]) return get1(t[rt].r,mid+1,r,xth); else return get1(t[rt].l,l,mid,xth-sum[t[rt].r]); } ll get2(int &rt,int l,int r,int xth)//后xth个数的值是多少 val { if (!rt) rt=++sz; if (!xth) return 0; if (xth>sum[rt]) return val[rt]; if (l==r) return xth*l*1ll; int mid=l+r>>1; if (xth<=sum[t[rt].r]) return get2(t[rt].r,mid+1,r,xth); else return get2(t[rt].l,l,mid,xth-sum[t[rt].r])+val[t[rt].r]; } int main() { freopen("grimoire.in","r",stdin); freopen("grimoire.out","w",stdout); n=read();m=read(); for (int i=1;i<=m;i++) { scanf("%s",c); int t=read(),p=read(); if (c[0]=='B'||c[1]=='B'||c[2]=='B') { ll k=query(tree[t],1,Y,p,Y); if (k<t) { update(tree[t],1,Y,p,1); int pos=get1(tree[t],1,Y,t+1); update(tr,1,Y,p,1); update(tr,1,Y,pos,-1); } else update(tree[t],1,Y,p,1); } else { ll k=query(tree[t],1,Y,p,Y); if (k<=t) { update(tree[t],1,Y,p,-1); int pos=get1(tree[t],1,Y,t); update(tr,1,Y,p,-1); update(tr,1,Y,pos,1); } else update(tree[t],1,Y,p,-1); } ll ans=get2(tr,1,Y,n); printf("%lld\n",ans); } return 0; }
版权声明：本文为xxzh原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。