NOI.AC NOIP模拟赛 第三场 补记
列队
题目大意：
给定一个\(n\times m(n,m\le1000)\)的矩阵，每个格子上有一个数\(w_{i,j}\)。保证\(w_{i,j}\)互不相同。\(q(q\le5\times10^5)\)次询问，每次给出\(x,y\)，询问有多少数满足在本行是第\(x\)大，在本列是第\(y\)大。
思路：
对每行、每列分别排序，求出每个数是本行、本列第几大。然后即可预处理答案。
时间复杂度\(\mathcal O(n^2\log n)\)。
源代码：
#include<cstdio>
#include<cctype>
#include<algorithm>
inline int getint() {
register char ch;
while(!isdigit(ch=getchar()));
register int x=ch^'0';
while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0');
return x;
}
const int N=1000;
int a[N][N],x[N][N],y[N][N],cnt[N][N];
std::pair<int,int> b[N];
int main() {
const int n=getint(),m=getint(),q=getint();
for(register int i=0;i<n;i++) {
for(register int j=0;j<m;j++) {
a[i][j]=getint();
b[j]=std::make_pair(a[i][j],j);
}
std::sort(&b[0],&b[m]);
for(register int j=0;j<m;j++) {
x[i][b[j].second]=m-j-1;
}
}
for(register int j=0;j<m;j++) {
for(register int i=0;i<n;i++) {
b[i]=std::make_pair(a[i][j],i);
}
std::sort(&b[0],&b[n]);
for(register int i=0;i<n;i++) {
y[b[i].second][j]=n-i-1;
}
}
for(register int i=0;i<n;i++) {
for(register int j=0;j<m;j++) {
cnt[x[i][j]][y[i][j]]++;
}
}
for(register int i=0;i<q;i++) {
const int x=getint()-1,y=getint()-1;
printf("%d\n",cnt[x][y]);
}
return 0;
}
染色
题目大意：
有一排\(n(n\le5000)\)个格子，有\(m(m\le5000)\)种颜色可以染，求有多少种染色方案，满足连续\(m\)个格子至少有\(2\)个格子颜色相同。
思路：
\(f_{i,j}\)表示考虑完前\(i\)个格子，最后有连续\(j\)个格子颜不同。
转移方程为：
\[f_{i,j}=f_{i-1,j-1}\times(m-j+1)+\sum_{k=j}^{m-1}f_{i-1,k}
\]
\]
前缀和优化即可。
时间复杂度\(\mathcal O(nm)\)。
源代码：
#include<cstdio>
#include<cctype>
#include<algorithm>
inline int getint() {
register char ch;
while(!isdigit(ch=getchar()));
register int x=ch^'0';
while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0');
return x;
}
typedef long long int64;
const int N=5001;
int f[N][N],g[N][N];
int main() {
const int n=getint(),m=getint(),p=getint();
f[0][0]=g[0][0]=1;
for(register int i=1;i<=n;i++) {
for(register int j=1;j<=std::min(i,m-1);j++) {
f[i][j]=((int64)f[i-1][j-1]*(m-j+1)+g[i-1][j])%p;
}
g[i][i]=f[i][i];
for(register int j=i-1;j>=1;j--) {
g[i][j]=(g[i][j+1]+f[i][j])%p;
}
}
printf("%d\n",g[n][1]);
return 0;
}
游戏
题目大意：
游戏中有\(n(n\le10^5)\)个角色，编号分别是\(1\sim n\)。在游戏里面角色一共有\(m+1(m\le10)\)个等级，分别是\(0\sim m\)，等级是由经验值决定的。形式化的，游戏有\(m\)个参数\(a_1\sim a_m\)，满足\(a_1<a_2<\ldots<a_m\)。若某个角色的经验值是\(x\)，那么他的等级就是满足\(x\ge a_i\)的最大的\(i\)，（当\(x<a1\)时是\(0\)）。
可以干两件事情：
- 打怪：带上编号在某一个区间\([l,r]\)内所有角色去打怪，这样结束之后这些角色都可以得到\(x\)的经验值；
- 氪金：充值之后把编号为\(p\)的角色的经验值魔改为\(x\)。
给出\(q(q\le10^5)\)询问，每个询问给出\([l,r]\)，求编号在\([l,r]\)区间内的所有角色的等级的和。
思路：
线段树维护每个角色的等级，以及升到下一级所需的经验值。
若升级经验值\(\le 0\)则暴力修改。
可以证明修改次数不超过\(\mathcal O((n+q)m)\)，因此复杂度是可以保证的。
源代码：
#include<cstdio>
#include<cctype>
#include<climits>
#include<algorithm>
inline int getint() {
register char ch;
while(!isdigit(ch=getchar()));
register int x=ch^'0';
while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0');
return x;
}
const int N=1e5+1,M=11;
int n,m,q,a[M];
class SegmentTree {
#define _left <<1
#define _right <<1|1
#define mid ((b+e)>>1)
private:
int min[N<<2],sum[N<<2],tag[N<<2];
void push_up(const int &p) {
min[p]=std::min(min[p _left],min[p _right]);
sum[p]=sum[p _left]+sum[p _right];
}
void push_down(const int &p) {
if(tag[p]==0) return;
min[p _left]-=tag[p];
min[p _right]-=tag[p];
tag[p _left]+=tag[p];
tag[p _right]+=tag[p];
tag[p]=0;
}
void maintain(const int &p,const int &b,const int &e) {
if(b==e) {
const int x=a[sum[p]+1]-min[p];
sum[p]=std::upper_bound(&a[1],&a[m]+1,x)-&a[1];
min[p]=sum[p]!=m?a[sum[p]+1]-x:INT_MAX;
return;
}
push_down(p);
if(min[p _left]<=0) maintain(p _left,b,mid);
if(min[p _right]<=0) maintain(p _right,mid+1,e);
push_up(p);
}
public:
void build(const int &p,const int &b,const int &e) {
if(b==e) {
const int x=getint();
sum[p]=std::upper_bound(&a[1],&a[m]+1,x)-&a[1];
min[p]=sum[p]!=m?a[sum[p]+1]-x:INT_MAX;
return;
}
build(p _left,b,mid);
build(p _right,mid+1,e);
push_up(p);
}
void add(const int &p,const int &b,const int &e,const int &l,const int &r,const int &x) {
if(b==l&&e==r) {
min[p]-=x;
tag[p]+=x;
return;
}
push_down(p);
if(l<=mid) add(p _left,b,mid,l,std::min(mid,r),x);
if(r>mid) add(p _right,mid+1,e,std::max(mid+1,l),r,x);
push_up(p);
}
void modify(const int &p,const int &b,const int &e,const int &x,const int &y) {
if(b==e) {
sum[p]=std::upper_bound(&a[1],&a[m]+1,y)-&a[1];
min[p]=sum[p]!=m?a[sum[p]+1]-y:INT_MAX;
return;
}
push_down(p);
if(x<=mid) modify(p _left,b,mid,x,y);
if(x>mid) modify(p _right,mid+1,e,x,y);
push_up(p);
}
int query(const int &p,const int &b,const int &e,const int &l,const int &r) {
if(b==l&&e==r) {
if(min[p]<=0) maintain(p,b,e);
return sum[p];
}
int ret=0;
push_down(p);
if(l<=mid) ret+=query(p _left,b,mid,l,std::min(mid,r));
if(r>mid) ret+=query(p _right,mid+1,e,std::max(mid+1,l),r);
push_up(p);
return ret;
}
#undef _left
#undef _right
#undef mid
};
SegmentTree t;
int main() {
n=getint(),m=getint(),q=getint();
for(register int i=1;i<=m;i++) a[i]=getint();
t.build(1,1,n);
for(register int i=0;i<q;i++) {
const int opt=getint();
if(opt==1) {
const int l=getint(),r=getint(),x=getint();
t.add(1,1,n,l,r,x);
}
if(opt==2) {
const int p=getint(),x=getint();
t.modify(1,1,n,p,x);
}
if(opt==3) {
const int l=getint(),r=getint();
printf("%d\n",t.query(1,1,n,l,r));
}
}
return 0;
}