头像

追着你行走




离线:1天前


活动打卡代码 AcWing 299. 裁剪序列

//这里填你的代码^^
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+5,inf=1<<29;
typedef long long ll;
typedef pair<int,int> pii;
#define mk(a,b) make_pair(a,b)
struct node{
    ll id,x,y;
    friend bool operator < (node a,node b) {
        return a.x+a.y>b.x+b.y;
    }
};
ll n,m,a[maxn],sum[maxn],st[maxn][30],c[maxn],f[maxn],q[maxn] ;
bool used[maxn] ;
void init() {
    for(int i=1;i<=n;i++) st[i][0]=a[i];
    for(int j=1;(1<<j)<=n;j++) {
        for(int i=1;i+(1<<(j-1))<=n;i++) {
            st[i][j]=max(st[i][j-1],st[i+(1<<(j-1))][j-1] ) ;
        }
    }
}
int ask(int l,int r) {
    int k=log2(r-l+1) ;
    int v=max(st[l][k],st[r-(1<<k)+1][k]);
    return v;
}
int main(){
    ios::sync_with_stdio(false); cin.tie(0);cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++) {
        cin>>a[i];
        if(a[i]>m) {
            cout<<-1; return 0;
        }
        sum[i]=sum[i-1]+a[i] ;
    }//st
    init();
    c[0]=1;
    for(int i=1;i<=n;i++) {
        for(int j=c[i-1];j<=n;j++) {
            if(sum[i]-sum[j-1]<=m) {
                c[i]=j; break;
            }
        }
    }
    priority_queue<node> pq;
    int h=1,t=0;
    for(int i=1;i<=n;i++) {
        //f[i]=inf;
        f[i]=f[c[i]-1]+ask(c[i],i)  ;
        while(h<=t&&sum[i]-sum[q[h]-1]>m) used[q[h]]=1,h++;//和限制 
        while(h<=t&&a[q[t]]<=a[i]) used[q[t]]=1,t--;
        q[++t]=i;
        if(h<t) pq.push((node){q[t-1],f[q[t-1] ],a[i] } );
        while(pq.size()&&(used[pq.top().id]||pq.top().y<ask(pq.top().id+1,i) ) ) 
            pq.pop();
        if(pq.size() ) f[i]=min(f[i],pq.top().x+pq.top().y);
    }
    cout<<f[n];
    return 0;
}
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~


活动打卡代码 AcWing 298. 围栏

#include<bits/stdc++.h>
using namespace std;
const int maxn=2e4+5,inf=1<<29;
typedef long long ll;
typedef pair<int,int> pii;
#define mk(a,b) make_pair(a,b)
int n,m,f[110][maxn],q[maxn] ;
struct rec{
    int l,p,s;
    friend bool operator < (rec a,rec b) {
        return a.s<b.s;
    }
}d[110] ;
int cal(int i,int k) {  return f[i-1][k]-d[i].p*k; }
int main(){
    ios::sync_with_stdio(false); cin.tie(0);cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=m;i++) cin>>d[i].l>>d[i].p>>d[i].s;
    sort(d+1,d+1+m);
    for(int i=1;i<=m;i++) { //阶段 
        int h=1,t=0;
        for(int k=max(0,d[i].s-d[i].l) ; k<d[i].s;k++){//所有可能断开的位置 
             while(h<=t&&cal(i,q[t])<=cal(i,k) ) t--;
             q[++t]=k; //位置 
        }

        for(int j=1;j<=n;j++) {
            f[i][j]=max(f[i-1][j],f[i][j-1]); //不刷
            if(j>=d[i].s) {
                while(h<=t&&q[h]+d[i].l<j) h++; //维护长度
                if(h>t) continue;
                int v=d[i].p*j+cal(i,q[h]);
                f[i][j]=max(f[i][j],v); 
            } 
        } 
    }
    cout<<f[m][n]<<'\n';
    return 0;
}
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~


活动打卡代码 AcWing 295. 清理班次

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+5,inf=1<<29;
typedef long long ll;
typedef pair<int,int> pii;
#define mk(a,b) make_pair(a,b)
int n,T;
pii d[maxn] ;
struct segtree{
    int l,r,mi;
}t[maxn*4] ;
void build(int rt,int l,int r) {
    t[rt].l=l,t[rt].r=r;
    if(l==r) {
        t[rt].mi=inf; //init inf
        return ;
    } 
    int mid=(l+r)/2; 
    build(rt*2,l,mid);
    build(rt*2+1,mid+1,r);
    t[rt].mi=min(t[rt*2].mi,t[rt*2+1].mi);
}
void update(int rt,int pos,int v) {
    if(t[rt].l==t[rt].r) {
        t[rt].mi=min(t[rt].mi,v); 
        return ;
    }
    int mid=(t[rt].l+t[rt].r)/2; 
    if(pos<=mid) update(rt*2,pos,v);
    else update(rt*2+1,pos,v);
    t[rt].mi=min(t[rt*2].mi , t[rt*2+1].mi);
}
int ask(int rt,int l,int r) {
    if(t[rt].l>=l&&t[rt].r<=r) {
        return t[rt].mi;
    }
    int mid=(t[rt].l+t[rt].r)/2 ;
    int v=inf;
    if(l<=mid) v=min(v,ask(rt*2,l,r) ) ;
    if(r>mid) v=min(v,ask(rt*2+1,l,r) ) ;
    return v;
}
int main(){
    ios::sync_with_stdio(false); cin.tie(0);cout.tie(0);
    cin>>n>>T; T++;
    for(int i=1;i<=n;i++) {
        int a,b; cin>>a>>b; a++,b++;
        d[i]=mk(b,a); //right left 
    }
    sort(d+1,d+1+n) ;
    build(1,1,T); 
    update(1,1,0) ; //init
    for(int i=1;i<=n;i++) {
        int l=d[i].second,r=d[i].first; //cout<<l<<' '<<r<<'\n';
        int v=ask(1,l-1,r) + 1 ; //最小值 
        update(1,r,v) ;
    }
    int ans=ask(1,T,T) ; 
    if(ans>=inf) cout<<-1;
    else cout<<ans;
    return 0;
}
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~



手写lower_bound也T了,求能过的正解



活动打卡代码 AcWing 296. 清理班次2

//这里填你的代码^^
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+5,inf=1<<29;
typedef long long ll;
typedef pair<int,int> pii;
#define mk(a,b) make_pair(a,b)
struct rec{
    int a,b,c;
    friend bool operator < (rec a,rec b) {
        return a.b<b.b; 
    }
}dat[maxn];
int tot,n,l,r ;
struct segtree{
    int l,r ; ll mi;
}t[maxn*4] ;
void build(int rt,int l,int r) {
    t[rt]=segtree{l,r,inf} ;
    if(l==r) {
        t[rt].mi=inf ;
        return ;
    }
    int mid=(t[rt].l+t[rt].r)/2 ;
    build(rt*2,l,mid);
    build(rt*2+1,mid+1,r);
    t[rt].mi=min(t[rt*2].mi,t[rt*2+1].mi) ;
}
void update(int rt,int pos,ll v) {
    if(t[rt].l==t[rt].r) {
        t[rt].mi=min(t[rt].mi,v) ;
        return ;
    }
    int mid=(t[rt].l+t[rt].r)/2;
    if(pos<=mid) update(rt*2,pos,v);
    else update(rt*2+1,pos,v) ;
    t[rt].mi=min(t[rt*2].mi,t[rt*2+1].mi) ; //pushup 
}
ll ask(int rt,int l,int r) { //查询最小值 
    if(t[rt].l>=l&&t[rt].r<=r) {
        return t[rt].mi;
    }
    int mid=(t[rt].l+t[rt].r)/2;
    ll ans=1ll<<32; 
    if(l<=mid) ans=min(ans,ask(rt*2,l,r) ) ;
    if(r>mid) ans=min(ans,ask(rt*2+1,l,r) ) ;
    return ans;
}
int main(){
    ios::sync_with_stdio(false); cin.tie(0);cout.tie(0);
    cin>>n>>l>>r; l+=2,r+=2;
    for(int i=1;i<=n;i++) {
        int a,b,c; cin>>a>>b>>c; a+=2,b+=2;
        if(a>r||b<l) continue ;
        a=max(a,l),b=min(r,b);
        dat[++tot]={a,b,c};
    }
    sort(dat+1,dat+1+tot); //从小到大   
    build(1,1,r) ;
    update(1,l-1,0); //init
    for(int i=1;i<=tot;i++) { //阶段 
        ll val=ask(1,dat[i].a-1,dat[i].b)+dat[i].c ; //决策 
        update(1,dat[i].b,val) ;
    }
    ll ans=ask(1,r,r) ;
    if(ans>=inf) cout<<-1;
    else cout<<ans; 
    return 0;
}
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~



Acwing + 296 +清理班次2


设f[x]表示覆盖[l,r]需要花费的最小代价。

把所有的数据按b~i~从小到大排序,并除去要求区间之处的数据。

状态转移方程为:
$$
f[b_i]=min(f[b_i],\min\limits_{a_i-1\leq x<b_i}{{f[x]}}+c_i)
$$
用线段树维护f[x]的最小值。初始值f[l-1]=0,即update(1,l-1,0)

线段树建树时初始为无穷大。目标状态即可ask(1,r,r)

代码实现

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+5,inf=1<<29;
typedef long long ll;
typedef pair<int,int> pii;
#define mk(a,b) make_pair(a,b)
struct rec{
    int a,b,c;
    friend bool operator < (rec a,rec b) {
        return a.b<b.b; 
    }
}dat[maxn];
int tot,n,l,r ;
struct segtree{
    int l,r ; ll mi;
}t[maxn*4] ;
void build(int rt,int l,int r) {
    t[rt]=segtree{l,r,inf} ;
    if(l==r) {
        t[rt].mi=inf ;
        return ;
    }
    int mid=(t[rt].l+t[rt].r)/2 ;
    build(rt*2,l,mid);
    build(rt*2+1,mid+1,r);
    t[rt].mi=min(t[rt*2].mi,t[rt*2+1].mi) ;
}
void update(int rt,int pos,ll v) {
    if(t[rt].l==t[rt].r) {
        t[rt].mi=min(t[rt].mi,v) ;
        return ;
    }
    int mid=(t[rt].l+t[rt].r)/2;
    if(pos<=mid) update(rt*2,pos,v);
    else update(rt*2+1,pos,v) ;
    t[rt].mi=min(t[rt*2].mi,t[rt*2+1].mi) ; //pushup 
}
ll ask(int rt,int l,int r) { //查询最小值 
    if(t[rt].l>=l&&t[rt].r<=r) {
        return t[rt].mi;
    }
    int mid=(t[rt].l+t[rt].r)/2;
    ll ans=1ll<<32; 
    if(l<=mid) ans=min(ans,ask(rt*2,l,r) ) ;
    if(r>mid) ans=min(ans,ask(rt*2+1,l,r) ) ;
    return ans;
}
int main(){
    ios::sync_with_stdio(false); cin.tie(0);cout.tie(0);
    cin>>n>>l>>r; l+=2,r+=2;
    for(int i=1;i<=n;i++) {
        int a,b,c; cin>>a>>b>>c; a+=2,b+=2;
        if(a>r||b<l) continue ; //数据的简化
        a=max(a,l),b=min(r,b);
        dat[++tot]={a,b,c};
    }
    sort(dat+1,dat+1+tot); //从小到大   
    build(1,1,r) ;
    update(1,l-1,0); //init
    for(int i=1;i<=tot;i++) { //阶段 
        ll val=ask(1,dat[i].a-1,dat[i].b)+dat[i].c ; //决策 
        update(1,dat[i].b,val) ;
    }
    ll ans=ask(1,r,r) ;
    if(ans>=inf) cout<<-1;
    else cout<<ans; 
    return 0;
}


活动打卡代码 AcWing 248. 窗内的星星

//这里填你的代码^^
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+5;
typedef long long ll;
struct segtree{
    ll ms,add;
}tree[maxn*8] ; 
struct node{
    ll x,h1,h2,c;
    node(ll a=0,ll b=0,ll c=0,ll d=0):x(a),h1(b),h2(c),c(d){}
    friend bool operator < (node a,node b) {
        return a.x<b.x ;
    }
}ar[maxn*2];
void pushdown(int rt ) {
    if(tree[rt].add) {
        tree[rt*2].ms=tree[rt].add+tree[rt*2].ms ;  //鏈€鍊肩淮鎶ゆ柟娉?
        tree[rt*2+1].ms=tree[rt].add+tree[rt*2+1].ms ;
        tree[rt*2].add+=tree[rt].add ;tree[rt*2+1].add+=tree[rt].add ;
        tree[rt].add=0 ;
    }
}
void updata(int rt,int l,int r,int st,int en,ll d) {
    if(l>=st&&r<=en) { tree[rt].ms=d+tree[rt].ms;tree[rt].add+=d;return;    }
    pushdown(rt) ;
    int mid=(l+r)/2 ;
    if(st<=mid) updata(rt*2,l,mid,st,en,d ) ;
    if(en>mid) updata(rt*2+1,mid+1,r,st,en,d) ;
    tree[rt].ms=max(tree[rt*2].ms,tree[rt*2+1].ms) ;
} 
ll arr[maxn*2],n,w,h ;//蹇呴』寮€ll涓嶇劧浼氭孩鍑?锛?
int main(){
    //ios::sync_with_stdio(false); cin.tie(0);cout.tie(0);
    while(~scanf("%d%d%d",&n,&w,&h) ) {
        memset(tree,0,sizeof(tree) ) ;//姣忕粍寮€濮嬫椂娓呯┖鏁扮粍 
        //cin>>n>>w>>h; 
        int len=0;
        for(int i=1;i<=n;i++) {
            ll x,y,c; cin>>x>>y>>c ;
            ar[++len]=node(x,y,y+h-1,c) ; arr[len]=y ;
            ar[++len]=node(x+w,y,y+h-1,-c) ; arr[len]=y+h-1;
        } sort(arr+1,arr+1+len) ;sort(ar+1,ar+1+len) ; 
        int cnt=unique(arr+1,arr+1+len)-arr-1 ;//绂绘暎鍖?
        ll ans=0;
        for(int i=1;i<=len;i++) {
            int h1=lower_bound(arr+1,arr+1+cnt,ar[i].h1)-arr ;
            int h2=lower_bound(arr+1,arr+1+cnt,ar[i].h2)-arr ;
            updata(1,1,cnt,h1,h2,ar[i].c) ;
            if(ar[i].x!=ar[i+1].x) //闃叉鍑虹幇x杈圭殑閲嶅悎鎯呭喌 
                ans=max(ans,tree[1].ms) ;
        } cout<<ans<<'\n' ;
    }
    return 0;
}
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~


活动打卡代码 AcWing 247. 亚特兰蒂斯

//这里填你的代码^^
#include<bits/stdc++.h>
using namespace std;
const int maxn=2e5+5,inf=1<<29;
typedef long long ll;
unordered_map<double,int > H;
set<double> st; 
int n,K ;
double num[maxn] ;
struct rec{
    double x,y1,y2; int add;
    friend bool operator < (rec a,rec b) {
        return a.x<b.x;
    }
}p[maxn];
struct Node{
    int l,r,add;
    double sum;
}t[maxn<<2];
void build(int rt,int l,int r) {
    t[rt]={l,r,0,0};
    if(l==r) return ;
    int mid=(l+r)/2;
    build(rt*2,l,mid) ;
    build(rt*2+1,mid+1,r);
}
void pushup(int rt) {
    if(t[rt].add>0) t[rt].sum=num[t[rt].r+1]-num[t[rt].l];
    else t[rt].sum=t[rt*2].sum+t[rt*2+1].sum ;
}
void update(int rt,int l,int r,int v) {
    if(t[rt].l>=l&&t[rt].r<=r) {
        t[rt].add+=v;
        pushup(rt) ;
        return ;
    } //pushdown
    int mid=(t[rt].l+t[rt].r)/2;
    if(l<=mid) update(rt*2,l,r,v);
    if(r>mid) update(rt*2+1,l,r,v);
    pushup(rt);
}
void init() {
    memset(p,0,sizeof p) ;
    memset(t,0,sizeof t) ;
    memset(num,0,sizeof num) ;
    st.clear();
    H.clear();
}
int main(){
    //ios::sync_with_stdio(false); cin.tie(0);cout.tie(0);
    while(cin>>n,n) {
        init();
        for(int i=1;i<=n;i++) {
            double a,b,c,d; cin>>a>>b>>c>>d;
            st.insert(b),st.insert(d) ; //去重 
            p[i]=rec{a,b,d,1};
            p[i+n]=rec{c,b,d,-1};
        }
        int tot=0;
        for(auto it:st) { 
            num[++tot]=it;
            H[it]=tot;
        } n*=2;
        sort(p+1,p+n+1);
        build(1,1,tot-1) ; //tot 为 y 的数据 
        double ans=0;
        for(int i=1;i<=n;i++) { 
            if(i>1) ans += t[1].sum*(p[i].x-p[i-1].x); 
            int l=H[p[i].y1],r=H[p[i].y2] ;
            update(1,l,r-1,p[i].add) ; //区间修改 
        }
        cout<<ans<<endl;
    }

    return 0;
}
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~



#include<bits/stdc++.h>
using namespace std;
const int maxn=5e5+2,inf=1<<29;
typedef long long ll;
typedef pair<ll,ll> pii;
#define mk(a,b) make_pair(a,b)
int n,m;
ll a[maxn],b[maxn],tree[maxn];
struct rec{
    int l,r; ll val;
}t[maxn<<2];
ll gcd(ll a,ll b) {
    return b?gcd(b,a%b):abs(a) ;
}
int lowbit(int x) { return x&-x; }
void add(ll pos,ll x) {
    for(int i=pos;i<=n;i+=lowbit(i) ) tree[i]+=x;
}
ll sum(ll pos) {
    ll ans=0;
    for(int i=pos;i;i-=lowbit(i) ) ans+=tree[i];
    return ans;
}
void build(int rt,int l,int r) {
    t[rt].l=l,t[rt].r=r;
    if(l==r) {
        t[rt].val=b[l]; //差分序列 
        return ;
    }
    int mid=(l+r)/2 ;
    build(rt*2,l,mid) ;
    build(rt*2+1,mid+1,r) ;
    t[rt].val=gcd(t[rt*2].val,t[rt*2+1].val) ;
}
void update(int rt,int pos,ll v) {
    if(t[rt].l==t[rt].r) {
        t[rt].val+=v;
        return ;
    }
    int mid=(t[rt].l+t[rt].r)/2;
    if(mid>=pos) update(rt*2,pos,v);
    else update(rt*2+1,pos,v) ;
    t[rt].val=gcd(t[rt*2].val,t[rt*2+1].val);//pushup 
} 
ll ask(int rt,int l,int r) {
    if(t[rt].l>=l&&t[rt].r<=r) {
        return t[rt].val;
    }
    int mid=(t[rt].l+t[rt].r)/2;
    ll a=0,b=0;
    if(mid>=l) a=ask(rt*2,l,r);
    if(mid<r) b=ask(rt*2+1,l,r) ;
    return gcd(a,b);//一定为正 
}
int main(){
    ios::sync_with_stdio(false); cin.tie(0);cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++) {
        cin>>a[i];
        b[i]=a[i]-a[i-1];
    } 
    build(1,1,n) ;
    ll v1,v2; int l,r;
    while(m--) {
        char op; cin>>op;
        if(op=='C') {
            ll d; cin>>l>>r>>d;
            update(1,l,d); 
            if(r<n) update(1,r+1,-d) ;
            add(l,d),add(r+1,-d);
        } else {
            cin>>l>>r;
            v1=a[l]+sum(l);
            v2=l<r?ask(1,l+1,r):0 ;
            cout<<gcd(v1,v2 )<<'\n';
        }
    }

    return 0;
}
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~



//这里填你的代码^^
#include<bits/stdc++.h>
using namespace std;
const int maxn=5e5+5,inf=1<<27;
typedef long long ll;
typedef pair<int,int> pii;
#define mk(a,b) make_pair(a,b)
int n,m,a[maxn];
struct rec{
    int l,r;
    int dat=-inf,lmax=-inf,rmax=-inf,sum=-inf;
}t[maxn<<2];
void pushup(rec &c,rec &a,rec &b) {
    c.sum=max(-inf,a.sum+b.sum);
    c.lmax=max(a.lmax,a.sum+b.lmax) ;
    c.rmax=max(b.rmax,a.rmax+b.sum);
    c.dat=max(a.rmax+b.lmax,max(a.dat,b.dat));
}
void build(int rt,int l,int r) {
    t[rt].l=l,t[rt].r=r;
    if(l==r) {
        t[rt].dat=t[rt].lmax=t[rt].rmax=t[rt].sum=a[l];
        return ;
    }
    int mid=(l+r)/2;
    build(rt*2,l,mid) ;
    build(rt*2+1,mid+1,r);
    pushup(t[rt],t[rt*2],t[rt*2+1] ) ;
}
rec ask(int rt,int l,int r) {
    if(t[rt].l>=l&&t[rt].r<=r) return t[rt];
    int mid=(t[rt].l+t[rt].r)/2;
    rec a,b,ans;
    if(l<=mid) a=ask(rt*2,l,r) ;
    if(r>mid) b=ask(rt*2+1,l,r) ;
    pushup(ans,a,b) ;
    return ans;
}
void update(int rt,int pos,int val) {
    if(t[rt].l==t[rt].r) {
        t[rt].dat=t[rt].lmax=t[rt].rmax=t[rt].sum=val;
        return ;
    }
    int mid=(t[rt].l+t[rt].r)/2;
    if(pos<=mid) update(rt*2,pos,val);
    else update(rt*2+1,pos,val) ;
    pushup(t[rt],t[rt*2],t[rt*2+1]) ;
}
int main(){
    ios::sync_with_stdio(false); cin.tie(0);cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i];
    build(1,1,n);
    while(m--) {
        int k,x,y; cin>>k>>x>>y;
        if(k==1) {
            if(x>y) swap(x,y);
            cout<<ask(1,x,y).dat<<'\n';
        } else {
            update(1,x,y);
        }
    } 
    return 0;
}
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~