专门做影评的网站,国内可访问的海外网站和应用,做网站 博客,淘宝指数查询Description Sylvia 是一个热爱学习的女♂孩子。 前段时间#xff0c;Sylvia 参加了学校的军训。众所周知#xff0c;军训的时候需要站方阵。 Sylvia 所在的方阵中有nm名学生#xff0c;方阵的行数为 n#xff0c;列数为 m。 为了便于管理#xff0c;教官在训练开始时Sylvia 参加了学校的军训。众所周知军训的时候需要站方阵。 Sylvia 所在的方阵中有n×m名学生方阵的行数为 n列数为 m。 为了便于管理教官在训练开始时按照从前到后从左到右的顺序给方阵中 的学生从 1 到 n×m 编上了号码参见后面的样例。即初始时第 iii 行第 jjj 列 的学生的编号是(i−1)×mj。 然而在练习方阵的时候经常会有学生因为各种各样的事情需要离队。在一天 中一共发生了 q 件这样的离队事件。每一次离队事件可以用数对(x,y)(1≤x≤n,1≤y≤m)描述表示第 x 行第 y 列的学生离队。 在有学生离队后队伍中出现了一个空位。为了队伍的整齐教官会依次下达 这样的两条指令 向左看齐。这时第一列保持不动所有学生向左填补空缺。不难发现在这条 指令之后空位在第 x 行第 m 列。向前看齐。这时第一行保持不动所有学生向前填补空缺。不难发现在这条 指令之后空位在第 n 行第 m 列。 教官规定不能有两个或更多学生同时离队。即在前一个离队的学生归队之后 下一个学生才能离队。因此在每一个离队的学生要归队时队伍中有且仅有第 n 行 第 m 列一个空位这时这个学生会自然地填补到这个位置。 因为站方阵真的很无聊所以 Sylvia 想要计算每一次离队事件中离队的同学 的编号是多少。 注意每一个同学的编号不会随着离队事件的发生而改变在发生离队事件后 方阵中同学的编号可能是乱序的。solution 正解线段树/树状数组/平衡树\(30\%\)开个 \(n*m\) 的数组模拟即可\(50\%\)发现只有500行有改动所以单独拿出这500行和最后一列模拟即可.\(80\%\)只有一行的话我们就开一个 \(mq\) 的数组然后树状数组维护每一个位置是否有人并且维护每一个位置的人的id这样就会产生很多空位询问就是查找第 \(y\) 个有人的位置的id二分树状数组 或 直接线段树查找第k大即可与 \(70\) 分不同的是还需要再维护最后一列像行一样维护即可\(100\%\)和 \(80\) 分类似想到有很多位置根本没有大的变动我们像之前一样我们把只需要出队的位置删除即可所以我们维护每一个位置是否被删但是不太好存所以用动态开点线段树标记删除位置然后像之前一样二分找出第 \(y\) 个有人的位置即可还有一个不同的是id数组需要动态维护所以开个vector存即可所以100和80的区别仅在于是否使用动态内存. 前50%和另外 20% #include algorithm
#include iostream
#include cstring
#include cstdlib
#include cstdio
#include cmath
#define RG register
using namespace std;
typedef long long ll;
const int N50005,M300005;
int n,m,Q,b[M],num0,tot;
struct node{int x,y;}e[M];namespace brute{ll a[505][N],line[N],r[N];void main(){for(int i1;itot;i)for(int j1;jm;j)a[i][j](ll)(b[i]-1)*mj;for(int i1;in;i)line[i](ll)(i-1)*mm;for(int P1;PQ;P){int xe[P].x,ye[P].y,hxy;printf(%lld\n,a[x][y]);hxya[x][y];for(int iy;im;i)r[i]a[x][i1];for(int iy;im;i)a[x][i]r[i];for(int ib[x];in;i)r[i]line[i1];for(int ib[x];in;i)line[i]r[i];line[n]hxy;for(int i1;itot;i)a[i][m]line[b[i]];}}
}namespace cheat{int id[M*2],tr[M*2];void add(int sta,int ad){for(int ista;imQ;i(i(-i)))tr[i]ad;}int qry(int sta){int ret0;for(int ista;i1;i-(i(-i)))rettr[i];return ret;}int midit(int k){int l1,rmQ,mid,tmp,ret0;while(lr){mid(lr)1;tmpqry(mid);if(tmpk)retmid,rmid-1;else lmid1;}return ret;}void main(){for(int i1;im;i)add(i,1),id[i]i;int cntm;for(int P1;PQ;P){int ye[P].y;int pmidit(y);printf(%d\n,id[p]);cnt;add(p,-1);add(cnt,1);id[cnt]id[p];}}
}void work(){scanf(%d%d%d,n,m,Q);for(int i1;iQ;i){scanf(%d%d,e[i].x,e[i].y);b[num]e[i].x;}sort(b1,bnum1);totunique(b1,bnum1)-b-1;for(int i1;in;i)e[i].xlower_bound(b1,btot1,e[i].x)-b;if(Q500)brute::main();else{if(n1)cheat::main();else brute::main();}
}int main(){work();return 0;
}100分 #include algorithm
#include iostream
#include cstdlib
#include cstring
#include cstdio
#include vector
#include cmath
#define RG register
#define il inline
#define iter iterator
#define Max(a,b) ((a)(b)?(a):(b))
#define Min(a,b) ((a)(b)?(a):(b))
using namespace std;
typedef long long ll;
const int N300005,M6000100;
vectorllS[N];
int n,m,Q,tot,root[N],ls[M],rs[M],v[M],cnt0;inline void Modify(int rt,int l,int r,int sa){if(!rt)rtcnt;v[rt];if(lr)return ;int mid(lr)1;if(samid)Modify(ls[rt],l,mid,sa);else Modify(rs[rt],mid1,r,sa);
}inline int qry(int rt,int l,int r,int k){if(lr)return l;int mid(lr)1;int summid-l1-v[ls[rt]];if(ksum)return qry(ls[rt],l,mid,k);return qry(rs[rt],mid1,r,k-sum);
}inline ll caline(int x){int rqry(root[n1],1,tot,x);Modify(root[n1],1,tot,r);return rn?1ll*(r-1)*mm:S[n1][r-n-1];
}
inline ll calrow(int x,int y){int rqry(root[x],1,tot,y);Modify(root[x],1,tot,r);return rm?1ll*(x-1)*mr:S[x][r-m];
}void work()
{int x,y;ll ret,tmp;scanf(%d%d%d,n,m,Q);totMax(n,m)Q;while(Q--){scanf(%d%d,x,y);if(ym){retcaline(x);S[n1].push_back(ret);printf(%lld\n,ret);}else{retcalrow(x,y);printf(%lld\n,ret);S[n1].push_back(ret);tmpcaline(x);S[x].push_back(tmp);}}
}int main()
{freopen(pp.in,r,stdin);freopen(pp.out,w,stdout);work();return 0;
}转载于:https://www.cnblogs.com/Yuzao/p/7920813.html
