A
枚举修改的区间更新答案即可。
#include<bits/stdc++.h>
#define CKE if(CHECK)
#define FRE if(FIL)
#define int long long
#define MX 200005
using namespace std;
const int CHECK=0,FIL=0;int read();
int n,m,k,res,a[MX],b[MX];
signed main(){
//ios::sync_with_stdio(false);
//cin.tie(0);cout.tie(0);
FRE freopen("ghost.in","r",stdin);
FRE freopen("ghost.out","w",stdout);
n=read();m=read();k=read();
for(int i=1;i<=n;i++){
a[i]=b[i]=read();
if(b[i]<k) b[i]=k;
a[i]+=a[i-1],b[i]+=b[i-1];
}
for(int i=m;i<=n;i++){
res=max(res,a[n]-a[i]+a[i-m]+b[i]-b[i-m]);
}printf("%lld\n",res);
return 0;
}
int read(){
int Ca=0;char Cr=' ';int Cf=1;
while(Cr<'0' || Cr>'9'){Cr=getchar();if(Cr=='-'){Cf=-1;}}
while(Cr>='0' && Cr<='9'){Ca=Ca*10+Cr-48;Cr=getchar();}
return Ca*Cf;
}
B
$f{0/1,i}{ }$ 表示不用/用了这一个物品的最小代价。
对于每个物品更新：
- $f{0,i}\leftarrow f{1,i}$。（这个不选）
- $f{1,i}\leftarrow f{0,i-v}+w$。（不连续不用扣）
- $f{1,i}\leftarrow f{0,i-v}+w-k$。（连续要扣）
#include<bits/stdc++.h>
#define CKE if(CHECK)
#define FRE if(FIL)
#define int long long
#define MN 105
#define MM 200005
using namespace std;
const int CHECK=0,FIL=0;int read();
int n,m,k,x,y,res,f[2][MM];
signed main(){
//ios::sync_with_stdio(false);
//cin.tie(0);cout.tie(0);
FRE freopen("item.in","r",stdin);//ex2大概率是狗屎
FRE freopen("item.out","w",stdout);
n=read();m=read();k=read();
memset(f,-0x3f,sizeof(f));f[0][0]=0;
for(int oo=1;oo<=n;oo++){
x=read();y=read();
for(int i=m;i>=x;i--){
f[0][i]=max(f[0][i],f[1][i]);
f[1][i]=max(f[1][i-x]+y-k,f[0][i-x]+y);
res=max(res,max(f[0][i],f[1][i]));
}
for(int i=x-1;i>=0;i--){
f[0][i]=max(f[0][i],f[1][i]);
f[1][i]=-1e15;
}
}printf("%lld\n",res);
return 0;
}
int read(){
int Ca=0;char Cr=' ';int Cf=1;
while(Cr<'0' || Cr>'9'){Cr=getchar();if(Cr=='-'){Cf=-1;}}
while(Cr>='0' && Cr<='9'){Ca=Ca*10+Cr-48;Cr=getchar();}
return Ca*Cf;
}
C
对于修改操作直接二分这个位置修改即可，下面是查询操作：
很显然两个数组都会是有序的。
二分到 p 表示前 k 大中第一个数组占了 p 个，第二个数组占了 k-p 个。
然后视情况二分即可，似乎要卡常。
#include<bits/stdc++.h>
#define CKE if(CHECK)
#define FRE if(FIL)
#define MX 1005
using namespace std;
const int CHECK=0,FIL=0;int read();
int n,m,x,y,k,p,q,a[MX][MX];
int fd(int i,int j){
int l=0,r=m;
while(l<r){
int mid=(l+r+1)>>1;
if(a[i][mid]<=j) l=mid;
else r=mid-1;
}return l;
}
signed main(){
//ios::sync_with_stdio(false);
//cin.tie(0);cout.tie(0);
FRE freopen("int.in","r",stdin);
FRE freopen("int.out","w",stdout);
n=read();m=read();int T=read();
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
a[i][j]=read();}
a[i][0]=-1;a[i][m+1]=2000000000;
}
while(T--) if(read()==1){
x=read();y=read();k=read();
int res=0,l=1,r=m+1;
while(l<=r){
p=(l+r)>>1;
q=(m<<1)-k-p+2;
//cout<<p<<','<<q<<'\n';
if(q>m+1){l=p+1;continue;}
if(q<1){r=p-1;continue;}
if(a[x][p-1]>a[y][q]){r=p-1;continue;}
if(a[y][q-1]>a[x][p]){l=p+1;continue;}
res=min(a[x][p],a[y][q]);break;
}
printf("%d\n",res);
}else{
x=read();y=read();
a[x][fd(x,y)]=y;
a[x][0]=0;
}
return 0;
}
int read(){
int Ca=0;char Cr=' ';int Cf=1;
while(Cr<'0' || Cr>'9'){Cr=getchar();if(Cr=='-'){Cf=-1;}}
while(Cr>='0' && Cr<='9'){Ca=Ca*10+Cr-48;Cr=getchar();}
return Ca*Cf;
}
D
发现集合中新加入 i 则 res\rightarrow res+(res+1)\times i。
可以开一个链表里面从小到大存储还不在集合的数，修改的时候一个一个跳即可。
至于找到第一个没用过的位置，可以从修改的左端点一直往右跳，然后按并查集路径压缩的方式更新路径上每个点右侧的点，然后就能过了。
#include<bits/stdc++.h>
#define CKE if(CHECK)
#define FRE if(FIL)
#define ll long long
#define MX 100000
#define MM 10000000
using namespace std;
const int CHECK=0,FIL=0;int read();
int n,l[MM+5],r[MM+5];
ll mod,res,a,b;bool f[MM+5];
int dfs(int t){
if(!f[t]) return t;
return r[t]=dfs(r[t]);
}
signed main(){
//ios::sync_with_stdio(false);
//cin.tie(0);cout.tie(0);
FRE freopen("homework.in","r",stdin);
FRE freopen("homework.out","w",stdout);
n=read();mod=read();
for(int i=1;i<=MM;i++) l[i]=i-1,r[i]=i+1;
while(n--){
a=read();b=read();
a=dfs(a);
while(a<=b){
res=(res+(res+1)*a)%mod;
r[l[a]]=r[a];
l[r[a]]=l[a];
f[a]=1;a=r[a];
}printf("%lld\n",res);
}
return 0;
}
int read(){
int Ca=0;char Cr=' ';int Cf=1;
while(Cr<'0' || Cr>'9'){Cr=getchar();if(Cr=='-'){Cf=-1;}}
while(Cr>='0' && Cr<='9'){Ca=Ca*10+Cr-48;Cr=getchar();}
return Ca*Cf;
}