ABC F 求调
  • 板块学术版
  • 楼主q1uple
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/8/31 21:45
  • 上次更新2024/9/1 10:52:43
查看原帖
ABC F 求调
539133
q1uple楼主2024/8/31 21:45

Rt,/kel Wa*28

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=4e6+6,mod=1e9+7,INF=2e9;
typedef unsigned long long ull;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<double,double> pdd;
#define qmi(a,b) a=min(a,b)
#define qma(a,b) a=max(a,b)
#define rep(i,l,r) for(int i=(l);i<=(r);i++)
#define atrep(i,l,r) for(int i=(r);i>=(l);i--)
#define vec vector<int>
#define pb push_back
int dp[N];
struct node{
    int x,y;
}g[N];
bool cmp(node x,node y){
    if(x.y!=y.y)return x.y<y.y;
    return x.x<y.x;
}
int h,w,n;
struct segment{
	struct nodde{
		int l,r,sum,id;
	}t[N*4];
	void pushup(int u){
		if(t[u*2].sum>t[u*2+1].sum){
            t[u].sum=t[u*2].sum;
            t[u].id=t[u*2].id;
        }
        else{
            t[u].sum=t[u*2+1].sum;
            t[u].id=t[u*2+1].id;
        }
	}
	void build(int u,int l,int r){
		t[u].l=l,t[u].r=r;
		if(l==r){
			return;
		}
		int mid=(l+r)>>1;
		build(u*2,l,mid);build(u*2+1,mid+1,r);
		pushup(u);
	}
	nodde query(int u,int l,int r){
		if(t[u].l>=l&&t[u].r<=r)	return t[u];
		int mid=(t[u].l+t[u].r)>>1;
        nodde sum={0,0,0};
		if(l<=mid){
            nodde ans=query(u*2,l,r);
            if(ans.sum>sum.sum){
                sum=ans;
            }
        }
		if(r>mid){
            nodde ans=query(u*2+1,l,r);
            if(ans.sum>sum.sum){
                sum=ans;
            }
        }
		return sum;
	}
    void modify(int u,int x,int val,int id){
        if(t[u].l==x){
            if(t[u].sum<val){
                t[u].sum=val;
                t[u].id=id;
            }
            return;
        }
        int mid=(t[u].l+t[u].r)>>1;
        if(x<=mid){
            modify(u*2,x,val,id);
        }else modify(u*2+1,x,val,id);
        pushup(u);
    }
}tr;
int pre[N];
void output(int sx,int sy,int ex,int ey){
    // cout<<sx<<" "<<sy<<" "<<ex<<" "<<ey<<endl;
    rep(i,1,ex-sx)    cout<<"D";
    rep(i,1,ey-sy)    cout<<"R";
}
void print(int begin,int fa){
    if(begin==0){
        output(g[begin].x,g[begin].y,g[fa].x,g[fa].y);
        return;
    }
    print(pre[begin],begin);
    output(g[begin].x,g[begin].y,g[fa].x,g[fa].y);
}
signed main(){
    cin>>h>>w>>n;
    rep(i,1,n)  cin>>g[i].x>>g[i].y;
    sort(g+1,g+n+1,cmp);
    int res=0,xid=0;
    tr.build(1,1,h);
    rep(i,1,n){
        int ans=tr.query(1,1,g[i].x).sum,id=tr.query(1,1,g[i].x).id;
        dp[i]=ans+1;
        pre[i]=id;
        if(res<dp[i]){
            res=dp[i];
            xid=i;
        }
        tr.modify(1,g[i].x,dp[i],i);
    }
    cout<<res<<endl;
    g[0].x=1,g[0].y=1;
    g[n+1].x=h,g[n+1].y=w;
    print(xid,n+1);
}
2024/8/31 21:45
加载中...