8.1 mx训练赛记录

__S08577__ · 2024-08-01 21:11:17 · 个人记录

A

题意

P9588

思路

• 对于操作一，观察数据范围，发现 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

题意

CF527C

思路

不难发现，横着切割和竖着切割是无关的，换句话说，无论选择哪一个长和宽，都能找到对应的碎片。所以，要找面积最大的碎片，就是求两边没被切割过的最大长度的积。

我们可以用 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;
}

/*

 */