9月17日数据结构专题考试题解
$ By~wch $
第一题：加法（线段树）
题目描述：
给一个 $ n $ 阶排列 $ b $ ，要求维护一个初值全为 $ 0 $ 的数组 $ a_i $ ，支持 $ q $ 次如下操作：
- 给出 $ l,r $ ，将 $ a_l,a_{l+1}...a_{r-1},a_{r} $ 全部加 \(1\) 。
- 给出 $ l,r $ ，查询 $ \sum_{i=l}^{r} \lfloor \frac{a_i}{b_i} \rfloor $
数据范围： $ n\leq 3\times 10^5$
$ solution: $
很让人头疼的一道题目，当时觉得第一个操作肯定是一个突破口，因为每次只加 $ 1 $ 。这是一个很好的性质，在结合一下题目的条件（ $ b $ 是个排列！），于是就算了一下最坏情况（不断区间加）的 $ \sum a_i =4\times 10^6 $ ，线段树每一次修改复杂度为 $ logn $ ，两者一乘复杂度可以接受。于是边只要看能不能实现这棵线段树了。
用线段树记录区间总和，用懒标记记录修改，然后每次加入时判断是否有元素达到了 $ b_i $ 权值需要加一，如果有就 $ pushdown $ 操作往下传，一直到那个要修改的叶子节点。（实现过程有点复杂，大家可以自己想，但是我自己都觉得常数可能过不了）
$ code: $
#include<iostream>
#include<cstdio>
#include<iomanip>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#include<ctime>
#include<cmath>
#include<vector>
#include<queue>
#include<map>
#include<set>
#define ll long long
#define db double
#define rg register int
#define zuo k<<1,l,mid
#define you k<<1|1,mid+1,r
#define midd int mid=(l+r)>>1
using namespace std;
int n,q,sx,sy,sv;
int mi[300005<<2];
int da[300005<<2];
int lz[300005<<2];
bool yz[300005<<2];
inline ll qr(){
register char ch; bool sign=0; register ll res=0;
while(!isdigit(ch=getchar()))if(ch=='-')sign=1;
while(isdigit(ch))res=res*10+(ch^48),ch=getchar();
if(sign)return -res; else return res;
}
inline void build(int k,int l,int r){
if(l==r){yz[k]=1; mi[k]=qr(); return ;}
midd; build(zuo); build(you);
mi[k]=min(mi[k<<1],mi[k<<1|1]);
}
inline void push(int k){
if(yz[k]){ //到达叶子节点，直接改
da[k]+=lz[k]/mi[k]; //加多少
lz[k]%=mi[k]; //还剩多少
return ;
}
rg l=k<<1,r=k<<1|1;
lz[l]+=lz[k]; lz[r]+=lz[k];
if(lz[l]>=mi[l]) push(l); //一直到需要更改的叶子节点
if(lz[r]>=mi[r]) push(r);
mi[k]=min(mi[l]-lz[l],mi[r]-lz[r]); //维护还需要多少次加操作达到上界
da[k]=da[l]+da[r]; lz[k]=0; //记得清零
}
inline void add(int k,int l,int r){
if(sx<=l&&r<=sy) ++lz[k];
else { midd; if(lz[k])push(k); //标记下放
if(sx<=mid) add(zuo);
if(sy>mid) add(you);
}
if(l!=r)mi[k]=min(mi[k<<1]-lz[k<<1],mi[k<<1|1]-lz[k<<1|1]);
if(lz[k]>=mi[k]) push(k); //mi数组：最少还需要多少次加操作，就会有元素达到上界
if(l!=r)da[k]=da[k<<1]+da[k<<1|1]; //区间和
}
inline void ask(int k,int l,int r){
if(sx<=l&&r<=sy){sv+=da[k]; return ;}
midd;
if(sx<=mid) ask(zuo);
if(sy>mid) ask(you);
}
int main(){
n=qr(); q=qr(); build(1,1,n);
for(rg i=1;i<=q;++i){
rg op=qr(); sx=qr(),sy=qr();
if(op==1) add(1,1,n);
else sv=0,ask(1,1,n);
if(op==2)printf("%d\n",sv);
}
return 0;
}
第二题：区间（并查集+计数）
题目描述：
给出一个长度为 $ n $ 的序列 $ a_i $ ，选出两个不相交的区间 $ [ l_1,r_1 ] $ 和 $ [l_2,r_2] $ ，获得的收益是两个区间的区间最小值的最小值。求所有不同的选法的收益之和模 \(10^9+7\) 。
数据范围：$ n\leq 10^6 , a_i \leq 10^9 $
$ solution: $
$ code: $
#include<iostream>
#include<cstdio>
#include<iomanip>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#include<ctime>
#include<cmath>
#include<vector>
#include<queue>
#include<map>
#include<set>
#define ll long long
#define db double
#define rg register int
using namespace std;
const int mod=1e9+7;
int n,tot,ans;
int s[1000005];
int t[1000005];
int r[1000005];
int g[1000005];
int f[1000005];
struct su{
int v,id;
inline bool operator <(const su &i)const{
return v>i.v;
}
}a[1000005];
inline int qr(){
register char ch; register bool sign=0; rg res=0;
while(!isdigit(ch=getchar()))if(ch=='-')sign=1;
while(isdigit(ch))res=res*10+(ch^48),ch=getchar();
if(sign)return -res; else return res;
}
inline int get(const int &x){
if(x==s[x])return x;
return s[x]=get(s[x]); //路径压缩
}
inline void bin(int x,int y){
x=get(x); y=get(y);
if(t[x]>t[y])swap(x,y); //按秩合并
tot-=g[t[x]]+g[t[y]];
t[y]+=t[x]; s[x]=y; r[y]=max(r[x],r[y]);
tot+=g[t[y]];
while(tot<0) tot+=mod;
while(tot>=mod) tot-=mod;
}
int main(){
n=qr();
for(rg i=1;i<=n;++i) g[i]=(g[i-1]+i)%mod;
for(rg i=1;i<=n;++i) f[i]=(g[i]+f[i-1])%mod;
for(rg i=1;i<=n;++i) a[i]=su{qr(),i};
sort(a+1,a+n+1);
for(rg i=1;i<=n;++i){
rg k=a[i].id; ++tot;
s[k]=k; t[k]=1; r[k]=k;
if(s[k-1]) bin(k-1,k);
if(s[k+1]) bin(k,k+1);
rg j=get(k),y=r[j]-k,x=t[j]-y-1,v=(tot-g[t[j]]+mod)%mod,tt=(ll)(x+1)*(y+1)%mod;
// 区间编号 右边长度 左边长度 其他区间可组成的片段个数 这个区间里包含k的片段数
(ans+=(ll)a[i].v*(((ll)(x+1)*f[y]+(ll)(y+1)*f[x]+(ll)tt*v)%mod)%mod)%=mod;
// 权值 左边片段贡献 右边片段贡献 其他区间贡献
}
printf("%d\n",ans);
return 0;
}
第三题：序列（可持久化trie+特殊性质）
$ solution: $
加班中…….
$ code: $
第四题：玉蟾宫（悬线法）
题目链接：洛谷 P4147 玉蟾宫
$ solution: $
已经写过题解了，在写悬线法详解的时候讲的。
挂个链接：最大子矩阵的两种求法
$ code: $
#include<iostream>
#include<cstdio>
#include<iomanip>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#include<ctime>
#include<cmath>
#include<vector>
#include<queue>
#include<map>
#include<set>
#define ll long long
#define db double
#define rg register int
using namespace std;
int n,m,ans;
int a[1005][1005];
int l[1005][1005];
int r[1005][1005];
int h[1005][1005];
inline ll qr(){
register char ch; bool sign=0; register ll res=0;
while(!isdigit(ch=getchar()))if(ch=='-')sign=1;
while(isdigit(ch))res=res*10+(ch^48),ch=getchar();
if(sign)return -res; else return res;
}
int main(){
n=qr(); m=qr(); char ch;
for(rg i=1;i<=n;++i){
for(rg j=1;j<=m;++j){
while((ch=getchar())!='F'&&ch!='R');
a[i][j]=(ch=='F');
if(a[i][j]){
l[i][j]=l[i][j-1]+1; //向左延伸
h[i][j]=h[i-1][j]+1; //向上延伸
}
}
}
for(rg i=1;i<=n;++i)
for(rg j=m;j>=1;--j)
if(a[i][j])r[i][j]=r[i][j+1]+1; //向右延伸
for(rg i=1;i<=n;++i){
for(rg j=m;j>=1;--j){
if(a[i-1][j])continue;
rg x=1e9,y=1e9;
for(rg k=i;a[k][j]&&k<=n;++k){
if(l[k][j]<x)x=l[k][j];
if(r[k][j]<y)y=r[k][j];
ans=max(ans,(x+y-1)*(k-i+1));
}
}
}
printf("%d\n",ans*3);
return 0;
}
第五题：Eden 的新背包问题
题目链接：洛谷 P4095 [HEOI2013] Eden 的新背包问题
$ solution: $
$ code: $
#include<iostream>
#include<cstdio>
#include<iomanip>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#include<ctime>
#include<cmath>
#include<vector>
#include<queue>
#include<map>
#include<set>
#define ll long long
#define db double
#define rg register int
using namespace std;
int n,m,q;
int a[1005];
int b[1005];
int c[1005];
int s[1005][10005];
int k[1005][10005];
int qv[10005];
int qt[10005];
inline int qr(){
register char ch; register bool sign=0; rg res=0;
while(!isdigit(ch=getchar()))if(ch=='-')sign=1;
while(isdigit(ch))res=res*10+(ch^48),ch=getchar();
if(sign)return -res; else return res;
}
inline void dp(int f[],int w,int v,int t){ //讲一个物品加入背包
for(rg i=0;i<w;++i){
rg l=1,r=0; qv[++r]=f[i]; qt[r]=0; //单调队列优化
for(rg j=i+w;j<=m;j+=w){
rg y=j/w,x=f[j]-y*v;
while(l<=r&&y-qt[l]>t)++l;
f[j]=max(f[j],y*v+qv[l]); //蓝书上有讲
while(l<=r&&qv[r]<=x)--r;
qv[++r]=x; qt[r]=y;
}
}
}
int main(){
n=qr(); m=1e4;
for(rg i=1;i<=n;++i)
a[i]=qr(),b[i]=qr(),c[i]=qr();
q=qr();
for(rg i=1;i<=n;++i){
for(rg j=0;j<=m;++j)
s[i][j]=s[i-1][j]; //记录每一步过程
dp(s[i],a[i],b[i],c[i]); //做一遍前缀
}
for(rg i=n;i>=1;--i){
for(rg j=0;j<=m;++j)
k[i][j]=k[i+1][j]; //记录每一步过程
dp(k[i],a[i],b[i],c[i]); //做一遍后缀
}
for(rg i=1;i<=q;++i){
rg x=qr(),y=x+2,v=qr(),ans=0;
for(rg j=0;j<=v;++j) //找到前后两个位置，合并
ans=max(ans,s[x][j]+k[y][v-j]);
printf("%d\n",ans);
}
return 0;
}