正解: 动态开点线段树
解题报告:
传送门! https://www.luogu.org/problemnew/show/P3960
因为最近学主席树的时候顺便 get 到了动态开点线段树? 刚好想起来很久很久以前就想做结果一直麻油做的这题,,, 所以就做下好了 QAQ
然后说下, 这题有很多种方法, 我目前是先只写个最傻逼的方法, 等学了 splay 什么的再来 upd 一下 QAQ(这题好像有, 线段树. 树状数组. splay 等各种方法, 我可能都会写只要我麻油咕 QAQ
然后就直接进入正题 QAQ
首先其实要知道动态开点线段树和线段树思想什么的都是一样儿的, 只是实现方法有一点儿区别(就是动态开点线段树节省点儿空间而已 QAQ
所以就考虑线段树怎么做昂 QAQ
首先可以发现, 每次变动之后, 有影响的只会是这个点, 这一行, 最后一列, 对趴
所以可以考虑对每一行 (不包括最后一个点 QAQ) 以及最后一列分别开个线段树
然后每次对当前操作(x,y), 先记录 ans, 并把这个编号从 x 这一行的线段树中删去, 加入第 n+1 棵树的最后一个位置, 然后把第 n+1 棵的 x 位置加入到第 x 行的最后一个位置
然后注意以下如果 x=n 也就是说它本来就在最后一列的时候就不用管了 QAQ
然后关于动态开点, 我提下 QAQ
考虑 q 的范围, 即最多有 q 个点加入, 那么线段树的长度最长为 max(n,m)+q
然后考虑到 nmq 范围, 所以动态开点, over
然后再说一个方法, 其实也是动态开点线段树, 只是还要简单点儿, 因为它还开了个 vector
然后有 vector 的话就每次压进去就好了鸭, 就是说线段树是个权值线段树记录被修改后的数字的, 具体的值在 vector 中查询一下就好
具体看代码 QAQ
然后记得开 ll,,, 我也不知道我什么猪脑子开了个 int 然后还麻油发现有什么不对,,, 我都佩服我自己了 QAQ
- #include<bits/stdc++.h>
- using namespace std;
- #define il inline
- #define rg register
- #define gc getchar()
- #define int long long
- #define rp(i,x,y) for(rg ll i=x;i<=y;++i)
- #define my(i,x,y) for(rg ll i=x;i>=y;--i)
- const int N=3e5+100,M=1e7+1000;
- int n,m,q,rt[N],nod_cnt,mx;
- struct sgtr{int ls,rs,sz;}tr[M];
- vector<int>v[N];
- il int read()
- {
- rg char ch=gc;rg int x=0;rg bool y=1;
- while(ch!='-' && (ch>'9' || ch<'0'))ch=gc;
- if(ch=='-')ch=gc,y=0;
- while(ch>='0' && ch<='9')x=(x<<1)+(x<<3)+(ch^'0'),ch=gc;
- return y?x:-x;
- }
- il void modify(int &nw,int l,int r,int to)
- {
- if(!nw)nw=++nod_cnt;++tr[nw].sz;if(l==r)return;
- int mid=(l+r)>>1;
- if(to<=mid)modify(tr[nw].ls,l,mid,to);else modify(tr[nw].rs,mid+1,r,to);
- }
- il int query(int nw,int l,int r,int to)
- {
- if(l==r)return l;int mid=(l+r)>>1,tmp=mid-l+1-tr[tr[nw].ls].sz;
- if(to<=tmp)return query(tr[nw].ls,l,mid,to);return query(tr[nw].rs,mid+1,r,to-tmp);
- }
- il int wk1(int x,int y)
- {
- int pos=query(rt[n+1],1,mx,x);modify(rt[n+1],1,mx,pos);
- int ans=(pos<=n?1ll*pos*m:v[n+1][pos-n-1]);
- return v[n+1].push_back(y?y:ans),ans;
- }
- il int wk2(int x,int y)
- {
- int pos=query(rt[x],1,mx,y);modify(rt[x],1,mx,pos);
- int ans=(pos<m?1ll*(x-1)*m+pos:v[x][pos-m]);
- return v[x].push_back(wk1(x,ans)),ans;
- }
- main()
- {
- // freopen("ld.in","r",stdin);freopen("ld.out","w",stdout);
- n=read();m=read();q=read();mx=max(n,m)+q;
- while(q--){int x=read(),y=read();printf("%lld\n",(y==m?wk1(x,0):wk2(x,y)));}
- return 0;
- }
先放下开 vector 做的代码 QAQ(然后不开 vector 的代码可能就咕了 QAQ?
来源: http://www.bubuko.com/infodetail-2969371.html