本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-08-01 21:11:17
A
题意
思路
对于操作一，观察数据范围，发现 $x \le 10^9$，所以不可能将 $1-x$ 全部放进序列。不妨只将 $x$ 放入序列，并记录前缀和。
对于操作二，不妨记录一共删去了多少数，然后暴力删除即可。
对于操作三，令 $z$ 加上删去的数的个数，然后二分查找即可。
对于操作四，我们可以使用
multiset直接查询最大值。
代码
#include<iostream>
#include<cstdio>
#include<cmath>
#include<string>
#include<cstring>
#include<iomanip>
#include<algorithm>
#include<vector>
#include<stack>
#include<map>
#include<queue>
#include<set>
using namespace std;
#define int long long
#define ll long long
#define Endl cout<<endl;
#define xy cout<<"xy";
#define yx cout<<"yx";
#define pii pair<int,int>
#define lowbit(x) x&(-x)
const int N=1e6+5;\/\/注意修改
const int mod=1e9+7;
const int Max=2e6+10;
int a[N],ss[N];
multiset<int> s;
signed main(){
\/\/ freopen("digit.in","r",stdin);
\/\/ freopen("digit,out","w",stdout);
int q;
cin>>q;
int cnt=0;
int num=0,idx=1;
while(q--){
int op,x;
cin>>op;
if(op!=4) cin>>x;
if(op==1){
a[++cnt]=x;
ss[cnt]=ss[cnt-1]+x;
s.insert(x);
}
if(op==2){
num+=x;
while(ss[idx]<=num&&idx<=cnt){
s.erase(s.find(a[idx]));
idx++;
}
}
if(op==3){
x+=num;
int index=lower_bound(ss+1,ss+1+cnt,x)-ss-1;
cout<<x-ss[index];
}
if(op==4){
cout<<*s.rbegin();
}
Endl
}
return 0;
}
\/\/唐儿祭天，法力无边
B
题意
思路
不难发现，横着切割和竖着切割是无关的，换句话说，无论选择哪一个长和宽，都能找到对应的碎片。所以，要找面积最大的碎片，就是求两边没被切割过的最大长度的积。
我们可以用 set 维护切割位置，用 multiset 维护切割出来的长度。
每次切割，我们先将切割位置放入set，找到其前一个切割位置 $a$，再找到其后一个切割位置 $b$，将 $a$ 和 $b$ 之间的长度删除，在增加两个长度（具体看代码，不好口述）。
最后，求出两条边的长度最大值求积即可。
代码
#include<iostream>
#include<cstdio>
#include<cmath>
#include<string>
#include<cstring>
#include<iomanip>
#include<algorithm>
#include<vector>
#include<stack>
#include<map>
#include<queue>
#include<set>
using namespace std;
#define int long long
#define ll long long
#define Endl cout<<endl;
#define xy cout<<"xy";
#define yx cout<<"yx";
#define pii pair<int,int>
#define lowbit(x) x&(-x)
const int N=1e6+5;\/\/注意修改
const int mod=1e9+7;
const int Max=2e6+10;
int n,m;
int id[N],tag[N],v[N];\/\/ id[i] 是当前点所在的块的编号
multiset <int> x,y;
set<int> lx,ly;
multiset<int>::iterator it;
signed main(){
\/\/ freopen("digit.in","r",stdin);
\/\/ freopen("digit,out","w",stdout);
int w,h;
cin>>w>>h>>n;
x.insert(w);
y.insert(h);
lx.insert(0);
lx.insert(w);
ly.insert(0);
ly.insert(h);
for(int i=1;i<=n;i++){
char op;
int t;
cin>>op>>t;
if(op=='H'){
ly.insert(t);
it=ly.find(t);
it--;
int l=*it;
it++;
it++;
int r=*it;
it=y.find(r-l);
y.erase(it);
y.insert(t-l);
y.insert(r-t);
}
if(op=='V'){
lx.insert(t);
it=lx.find(t);
it--;
int l=*it;
it++;
it++;
int r=*it;
it=x.find(r-l);
x.erase(it);
x.insert(t-l);
x.insert(r-t);
}
it=x.end();
it--;
int l=*it;
it=y.end();
it--;
int r;
r=*it;
cout<<l*r<<endl;
}
return 0;
}
D
题意
线段树，区间加，区间最值，区间和，区间除。
思路
这里只叙述区间除。
不难发现，$max-\left \lfloor \frac{max}{d} \right \rfloor=min-\left \lfloor \frac{min}{d} \right \rfloor $，区间除可以退化成区间减。
代码
#include<iostream>
#include<cstdio>
#include<cmath>
#include<string>
#include<cstring>
#include<iomanip>
#include<algorithm>
#include<vector>
#include<stack>
#include<map>
#include<queue>
using namespace std;
#define int long long
#define ll long long
#define Endl cout<<endl;
#define xy cout<<"xy";
#define yx cout<<"yx";
#define pii pair<int,int>
#define lowbit(x) x&(-x)
const int N=1e6+5;\/\/注意修改
const int mod=1e9+7;
const int Max=2e6+10;
int a[N];
struct tree{
int l,r;
int add,sum,maxx,minn;
}tr[N<<2];
void pushup(int rt){
tr[rt].sum=tr[rt<<1].sum+tr[rt<<1|1].sum;
tr[rt].maxx=max(tr[rt<<1].maxx,tr[rt<<1|1].maxx);
tr[rt].minn=min(tr[rt<<1].minn,tr[rt<<1|1].minn);
}
void build(int rt,int l,int r){
tr[rt].l=l;
tr[rt].r=r;
tr[rt].add=0;
if(l==r){
tr[rt].sum=a[l];
tr[rt].maxx=a[l];
tr[rt].minn=a[l];
return ;
}
int mid=(l+r)>>1;
build(rt<<1,l,mid);
build(rt<<1|1,mid+1,r);
pushup(rt);
}
void pushdown(int rt){
if(tr[rt].add==0) return ;
tr[rt<<1].add+=tr[rt].add;
tr[rt<<1|1].add+=tr[rt].add;
tr[rt<<1].sum+=tr[rt].add*(tr[rt<<1].r-tr[rt<<1].l+1);
tr[rt<<1|1].sum+=tr[rt].add*(tr[rt<<1|1].r-tr[rt<<1|1].l+1);
tr[rt<<1].maxx+=tr[rt].add;
tr[rt<<1|1].maxx+=tr[rt].add;
tr[rt<<1].minn+=tr[rt].add;
tr[rt<<1|1].minn+=tr[rt].add;
tr[rt].add=0;
}
void Add(int rt,int l,int r,int x){
if(tr[rt].l>=l&&tr[rt].r<=r){
tr[rt].add+=x;
tr[rt].sum+=x*(tr[rt].r-tr[rt].l+1);
tr[rt].maxx+=x;
tr[rt].minn+=x;
return ;
}
pushdown(rt);
int mid=(tr[rt].l+tr[rt].r)>>1;
if(l<=mid) Add(rt<<1,l,r,x);
if(r>mid) Add(rt<<1|1,l,r,x);
pushup(rt);
}
void Div(int rt,int l,int r,int x){
if(tr[rt].l>=l&&tr[rt].r<=r&&tr[rt].maxx-floor(1.0*tr[rt].maxx\/x)==tr[rt].minn-floor(1.0*tr[rt].minn\/x)){
int d=floor(1.0*tr[rt].maxx\/x)-tr[rt].maxx;
tr[rt].add+=d;
tr[rt].sum+=d*(tr[rt].r-tr[rt].l+1);
tr[rt].maxx+=d;
tr[rt].minn+=d;
return ;
}
pushdown(rt);
int mid=(tr[rt].l+tr[rt].r)>>1;
if(l<=mid) Div(rt<<1,l,r,x);
if(r>mid) Div(rt<<1|1,l,r,x);
pushup(rt);
}
int query(int rt,int l,int r){
if(tr[rt].l>=l&&tr[rt].r<=r){
return tr[rt].sum;
}
if(tr[rt].l==tr[rt].r) return 0;
pushdown(rt);
int mid=(tr[rt].l+tr[rt].r)>>1;
int res=0;
if(l<=mid) res+=query(rt<<1,l,r);
if(r>mid) res+=query(rt<<1|1,l,r);
pushup(rt);
return res;
}
int Query(int rt,int l,int r){
if(tr[rt].l>=l&&tr[rt].r<=r){
return tr[rt].minn;
}
if(tr[rt].l==tr[rt].r) return 0;
pushdown(rt);
int mid=(tr[rt].l+tr[rt].r)>>1;
int res=0x3f3f3f3f;
if(l<=mid) res=min(res,Query(rt<<1,l,r));
if(r>mid) res=min(res,Query(rt<<1|1,l,r));
pushup(rt);
return res;
}
signed main(){
\/\/ freopen("digit.in","r",stdin);
\/\/ freopen("digit,out","w",stdout);
int n,q;
cin>>n>>q;
for(int i=1;i<=n;i++){
cin>>a[i];
}
build(1,1,n);
while(q--){
int op;
cin>>op;
int l,r,c,d;
if(op==1){
cin>>l>>r>>c;
l++;
r++;
Add(1,l,r,c);
}
if(op==2){
cin>>l>>r>>d;
l++;
r++;
Div(1,l,r,d);
}
if(op==3){
cin>>l>>r;
l++;
r++;
cout<<Query(1,l,r);
}
if(op==4){
cin>>l>>r;
l++;
r++;
cout<<query(1,l,r);
}
Endl
\/\/ Endl
\/\/ cout<<query(1,1,n);
\/\/ Endl
\/\/ Endl
}
return 0;
}
\/*
*\/
鲁ICP备2025150228号