2.19 simulation summary

Preface

expect ：100+35+20=155
actual ：0+35+20
rnk22
Big score , ha-ha .
It's too good to write and hang the opposite shot and the positive solution together .

title

Barbecue time （barbeque）

Questions I have done before .
However, the simplest transfer hanging without turning over is too much .

Sequence selection （sequence）

I always thought it would be double ended dfs.
However, there is no idea …

The positive solution is amazing .
Consider the elements from small to large .
To $i$ when ,$<i$ The elements of are equivalent , In a continuous segment composed of these elements , We only focus on a few elements in each paragraph , And don't care what you choose .
So you can press it like this . During the transfer process, it is necessary to decode again 、 code , It's disgusting .
And the complexity of writing directly is not acceptable , Only 70, Maybe the inner layer cannot $O(paragraphCount)$ , Must have $O(1)$.
It seems that you can do , But it's disgusting to write about my wife …

Sequence order （sequence）

Cancer data structure problem .
I always thought it was a block or a Kodori tree , Not at all , ha-ha .

Consider tree over tree , Balance tree sets weight segment tree .
Segment tree splitting is required 、 Merger, etc .
I can't write it at all

Code

T1

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define ok debug("OK\n")
inline ll read(){
    
  ll x(0),f(1);char c=getchar();
  while(!isdigit(c)){
    if(c=='-')f=-1;c=getchar();}
  while(isdigit(c)){
    x=(x<<1)+(x<<3)+c-'0';c=getchar();}
  return x*f;
}
const int N=2e5+100;
const int mod=998244353;
const int inf=1e9;

int n,m;

int f[2][N][2],now,pre;
struct node{
    
  int l,r;
  bool operator < (const node oth)const{
    return l<oth.l;}
}p[N];
int q[N],st,ed;

signed main(){
    
  freopen("barbecue.in","r",stdin);
  freopen("barbecue.out","w",stdout);
  n=read();m=read();
  for(int i=1;i<=m;i++) p[i].l=read(),p[i].r=read();
  p[++m]=(node){
    2*n,2*n};
  sort(p+1,p+1+m);
  memset(f,0x3f,sizeof(f));
  f[1][0][1]=0;now=1;
  //f[1][0][0]=0
  for(int k=1;k<=m;k++){
    
    //printf("\n------------\nk=%d (%d %d)\n",k,p[k].l,p[k].r);
    swap(now,pre);
    memset(f[now],0x3f,sizeof(f[now]));

    int d=p[k].r-p[k-1].r;
    for(int i=0;i<=n;i++){
    
      f[now][i][0]=f[pre][i][0];
      if(i+d<=n) f[now][i+d][1]=f[pre][i][1];
    }
    
    int l=p[k].l-p[k-1].r,r=p[k].r-p[k-1].r;
    st=1;ed=0;
    //printf("one time : 1->0 (%d %d)\n",l,r);
    for(int i=0;i<=n;i++){
    //one time : 1->0
      while(st<=ed&&i-q[st]>r) ++st;
      if(i-l>=0){
    
	int o=i-l;
	while(st<=ed&&f[pre][q[ed]][1]>=f[pre][o][1]) --ed;
	q[++ed]=o;
      }
      if(st<=ed) f[now][i][0]=min(f[now][i][0],f[pre][q[st]][1]+1);
      //printf(" i=%d (%d %d) j=%d f=%d pre=%d\n",i,st,ed,q[st],f[now][i][0],f[pre][q[st]][1]);
    }

    l=0,r=p[k].r-p[k].l;
    st=1,ed=0;
    for(int i=0;i<=n;i++){
    //one time : 0->1
      while(st<=ed&&i-q[st]>r) ++st;
      if(i-l>=0){
    
	int o=i-l;
	while(st<=ed&&f[pre][q[ed]][0]>=f[pre][o][0]) --ed;
	q[++ed]=o;
      }
      if(st<=ed) f[now][i][1]=min(f[now][i][1],f[pre][q[st]][0]+1);
    }

    l=p[k].l-p[k-1].r,r=p[k].r-p[k-1].r;
    st=1,ed=0;
    for(int i=0;i<=n;i++){
    //two time : 1->0->1
      while(st<=ed&&i-q[st]>r) ++st;
      if(i-l>=0){
    
	int o=i-l;
	while(st<=ed&&f[pre][q[ed]][1]>=f[pre][o][1]) --ed;
	q[++ed]=o;
      }
      if(st<=ed) f[now][i][1]=min(f[now][i][1],f[pre][q[st]][1]+2);
    }

    l=0,r=p[k].r-p[k].l;
    st=1,ed=0;
    for(int i=0;i<=n;i++){
    //two time : 0->1->0
      while(st<=ed&&i-q[st]>r) ++st;
      if(i-l>=0){
    
	int o=i-l;
	while(st<=ed&&f[pre][q[ed]][0]>=f[pre][o][0]) --ed;
	q[++ed]=o;
      }
      if(st<=ed) f[now][i][0]=min(f[now][i][0],f[pre][q[st]][0]+2);
    }
    //for(int i=0;i<=n;i++){
    
      //for(int o=0;o<=1;o++) printf(" i=%d op=%d f=%d\n",i,o,f[now][i][o]);
    //}
  }
  int ans=min(f[now][n][0],f[now][n][1]);
  if(ans>1e9) puts("NO");
  else{
    
    puts("YES");
    printf("%d\n",ans);
  }
  return 0;
}
/* #include<bits/stdc++.h> using namespace std; #define ll long long #define debug(...) fprintf(stderr,__VA_ARGS__) const int N=2e6+100; const int mod=1e9+7; inline ll read(){ ll x(0),f(1);char c=getchar(); while(!isdigit(c)){if(c=='-')f=-1;c=getchar();} while(isdigit(c)){x=(x<<1)+(x<<3)+c-'0';c=getchar();} return x*f; } #define r rand() int n,m; int fa[N]; int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);} vector<int>v[N]; void dfs(int x,int f){ fa[x]=f; for(int to:v[x]){ if(to==f) continue; dfs(to,x); } return; } int tp[10]={0,10,50,100,500,1000}; set<int>s; signed main(signed int argc, char * argv[]){ #ifndef ONLINE_JUDGE freopen("a.in","w",stdout); //freopen("a.out","w",stdout); #endif srand(time(0)*1000); int o=tp[rand()%5+1]; n=2000;m=rand()%o+1; while(m--) s.insert(rand()%(n+1)); m=s.size()/2; printf("%d %d\n",n/2,m); int clo(0); for(int x:s){ printf("%d ",x); ++clo; if(clo%2==0) puts(""); if(clo==m*2) break; } return 0; } /* 10 1 3 2 0 -2 -1 -5 4 1 -5 1 -2 3 1 1 -1 1 -2 -5 -3 3 */

T2

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
inline ll read(){
    
	ll x(0),f(1);char c=getchar();
	while(!isdigit(c)){
    if(c=='-') f=-1;c=getchar();}
	while(isdigit(c)){
    x=(x<<1)+(x<<3)+c-'0';c=getchar();}
	return x*f;
}

const int N=5e6+100;
const int mod=1e9+7;

int n;

int a[50],bel[50][50],up[50][50],len[50][50],num[50],pai[50],pos[50],pl[50];
void decode(int k,int s,int *x){
    
	for(int i=1;i<=num[k];i++){
    
		x[i]=(i==num[k])?s:s%(len[k][i]+1);
		s/=(len[k][i]+1);
	} 
	return;
}
int code(int k,int *x){
    
	int res(0);
	for(int i=num[k];i>=1;i--) res=res*(len[k][i]+1)+x[i];
	return res;
}

int cnt[50],ncnt[50];
ll mn[2][N],tot[2][N],now,pre;
inline void update(int s,int ns){
    
	if(mn[now][ns]>mn[pre][s]){
    
		mn[now][ns]=mn[pre][s];
		tot[now][ns]=tot[pre][s];
	}
	else if(mn[now][ns]==mn[pre][s]){
    
		tot[now][ns]+=tot[pre][s];
	}
	return;
}

inline int calc(int x){
    
	int res(0);
	while(x){
    
		++res;
		x-=x&-x;
	}
	return res;
}
int ans[55],res[55];
signed main(){
    
	freopen("sequence.in","r",stdin);
	freopen("sequence.out","w",stdout);
	n=read();
	for(int i=1;i<=n;i++) a[i]=read();
	for(int k=1;k<=n+1;k++){
    
		pl[a[k]]=k;
		for(int i=1;i<=n;i++){
    
			if(a[i]==k) pos[k]=num[k];
			if(a[i]>=k) continue;
			if(i==1||a[i-1]>=k) ++num[k];
			bel[k][i]=num[k];
			len[k][num[k]]++;
		}
		pai[k]=1;
		for(int i=1;i<=num[k];i++) pai[k]*=(len[k][i]+1);
		//for(int i=1;i<=n;i++) printf("%d ",bel[k][i]);puts("");
	}
	for(int k=1;k<=n;k++){
    
		for(int i=1;i<=n;i++){
    
			up[k][bel[k][i]]=bel[k+1][i];
		}
		//for(int i=1;i<=num[k];i++) printf("%d ",up[k][i]);puts(""); 
	}
	
	mn[1][0]=0;tot[1][0]=1;now=1;
	for(int k=0;k<n;k++){
    
		swap(now,pre);
		memset(mn[now],0x3f,sizeof(mn[now]));
		memset(tot[now],0,sizeof(tot[now]));
		//printf("\n--------------\nk=%d\n",k);
		for(int s=0;s<=pai[k+1];s++){
    
			//printf(" s=%d mn=%lld\n",s,mn[pre][s])
			if(mn[pre][s]>1e9) continue;
			decode(k+1,s,cnt);
			//printf("cnt: ");for(int i=1;i<=num[k+1];i++) printf("%d ",cnt[i]);puts("");
			for(int i=1;i<=num[k+2];i++) ncnt[i]=0;
			for(int i=1;i<=num[k+1];i++) ncnt[up[k+1][i]]+=cnt[i];
			//printf("ncnt: ");for(int i=1;i<=num[k+1];i++) printf("%d ",ncnt[i]);puts("");
			int ns=code(k+2,ncnt);
			update(s,ns);
			int w(0);
			for(int i=1;i<=pos[k+1];i++) w+=cnt[i];
			ncnt[bel[k+2][pl[k+1]]]++;
			mn[pre][s]+=w;
			//printf("ncnt: w=%d ",w);for(int i=1;i<=num[k+1];i++) printf("%d ",ncnt[i]);puts("");
			ns=code(k+2,ncnt);
			update(s,ns);
			//puts("");
		}
	}
	for(int i=1;i<=n;i++) printf("%lld %lld\n",mn[now][i],tot[now][i]);
}
/* 6 3 1 4 6 2 5 */