自己的 AC 做法似乎离正解偏了十万八千里...... 不管怎样还是记录下来吧.
题意:
思路:
代码:
- #include <bits/stdc++.h>
- using namespace std;
- #define iinf 2000000000
- #define linf 1000000000000000000LL
- #define ulinf 10000000000000000000ull
- #define MOD1 1000000007LL
- #define mpr make_pair
- typedef long long LL;
- typedef unsigned long long ULL;
- typedef unsigned long UL;
- typedef unsigned short US;
- typedef pair <int , int> pii;
- clock_t __stt;
- inline void TStart(){__stt=clock();}
- inline void TReport(){printf("\nTaken Time : %.3lf sec\n",(double)(clock()-__stt)/CLOCKS_PER_SEC);}
- template <typename T> T MIN(T a,T b){return a<b?a:b;}
- template <typename T> T MAX(T a,T b){return a>b?a:b;}
- template <typename T> T ABS(T a){return a>0?a:(-a);}
- template <typename T> void UMIN(T &a,T b){if(b<a) a=b;}
- template <typename T> void UMAX(T &a,T b){if(b>a) a=b;}
- const int lg=17,inf=1000000;
- vector <int> prt[100005],lev[100005];
- int n,m,q,l[100005],mx[lg][100005],dis[2][100005],nx[100005];
- struct data{
- int ld,rd,lc,rc;
- void set(int LD,int RD,int LC,int RC){
- ld=LD;rd=RD;lc=LC;rc=RC;
- if(!ld) lc=inf;
- }
- void tran(data L,data R){
- if(L.ld==-1) L.lc=L.rc=inf;
- if(R.ld==-1) R.lc=R.rc=inf;
- int nlc=MIN(lc+L.lc,rc+R.lc),nrc=MIN(lc+L.rc,rc+R.rc);
- set((L.ld==-1?R.ld:L.ld),(L.ld==-1?R.rd:L.rd),nlc,nrc);
- }
- };
- vector <data> dp[lg][100005][2];
- int prev(int i,int l){
- // before or equal
- int j;
- for(j=lg-1;j>=0;--j){
- if(i-(1<<j)>=-1 && mx[j][i-(1<<j)+1]<l){
- i-=(1<<j);
- }
- }
- return i;
- }
- int nxt(int i,int l){
- // after
- int j;
- ++i;
- for(j=lg-1;j>=0;--j){
- if(i+(1<<j)<=n && mx[j][i]<l){
- i+=(1<<j);
- }
- }
- return i;
- }
- int qrymax(int l,int r){
- int le;
- for(le=0;(1<<(le+1))<r-l+1;++le);
- return MAX(mx[le][l],mx[le][r-(1<<le)+1]);
- }
- int qrydis(int s,int t,int le){
- int cnt=0;
- if(s>t) swap(s,t);
- while(s<t){
- if(le==l[s]){
- cnt+=dis[1][s]%inf;
- s=nxt(s,le+1);
- }
- else{
- ++cnt;
- s=nxt(s,le);
- }
- }
- if(t<s && le==l[t]){
- cnt-=dis[1][t]%inf;
- }
- return cnt;
- }
- data qrydisV(int s,int le){
- data cur,nxt;
- if(s==n-1)
- cur.set(s-1,0,1,0);
- else
- cur.set(s,0,0,1);
- int i;
- for(i=lg-1;i>=0 && cur.ld!=-1;--i){
- nxt=cur;
- nxt.tran(dp[i][nxt.ld][0][nxt.rd],dp[i][nxt.ld][1][nxt.rd]);
- if(nxt.ld!=-1 && (nxt.rd?lev[nxt.ld][nxt.rd-1]:-1)<le)
- cur=nxt;
- if(cur.ld!=-1 && lev[cur.ld][cur.rd]>=le) break;
- }
- if(cur.ld!=-1 && lev[cur.ld][cur.rd]<le) cur.ld=-1;
- return cur;
- }
- int main(){
- // inputting start
- // 数据结构记得初始化! n,m 别写反!
- int i,j,k,fsv=-1,fsp=-1,scv=-1;
- scanf("%d%d%d",&n,&m,&q);
- for(i=1;i<=n;++i){
- scanf("%d",l+i);
- --l[i];
- if(l[i]>fsv){
- fsv=l[i];
- fsp=i;
- }
- else if(l[i]>scv){
- scv=l[i];
- }
- }
- l[fsp]=scv;
- l[0]=m++;
- ++n;
- #ifdef LOCAL
- TStart();
- #endif
- // calculation start
- // 数据结构记得初始化! n,m 别写反!
- for(i=0;i<n;++i) mx[0][i]=l[i];
- for(i=1;i<lg;++i){
- for(j=0;j<n;++j){
- int nl=j+(1<<(i-1));
- if(nl<n)
- mx[i][j]=MAX(mx[i-1][j],mx[i-1][nl]);
- else
- mx[i][j]=mx[i-1][j];
- }
- }
- for(i=n-1;i>=0;--i){
- nx[i]=nxt(i,l[i]+1);
- int suc=nxt(i,l[i]);
- if(suc>=n)
- dis[1][i]=inf;
- else if(l[suc]>l[i])
- dis[1][i]=1;
- else
- dis[1][i]=dis[1][suc]+1;
- for(j=i+1;j<suc;j=nx[j]){
- prt[i].push_back(j);
- lev[i].push_back(l[j]);
- }
- if(suc<n){
- prt[i].push_back(suc);
- lev[i].push_back(l[i]);
- }
- dp[0][i][0].resize(prt[i].size());
- dp[0][i][1].resize(prt[i].size());
- for(j=0;j<(int)prt[i].size()-1;++j){
- dp[0][i][0][j].set(i,j+1,0,1);
- dp[0][i][1][j].set(i,j+1,1,MIN(2,dis[1][prt[i][j]]));
- }
- }
- for(i=0;i<n;++i){
- int prd=prev(i,l[i]+1),prv=prev(i-1,l[i]),d=(int)prt[i].size()-1;
- if(prv==-1)
- dis[0][i]=inf;
- else if(l[prv]>l[i])
- dis[0][i]=1;
- else
- dis[0][i]=dis[0][prv]+1;
- if(d==-1) continue;
- if(prd!=-1 && lev[prd].back()<=l[i]) prd=prev(prd-1,l[i]+1);
- if(prd==-1 || lev[prd].empty() || lev[prd].back()<=l[i])
- dp[0][i][0][d].ld=dp[0][i][1][d].ld=-1;
- else{
- int nd=lower_bound(lev[prd].begin(),lev[prd].end(),l[i]+1)-lev[prd].begin();
- int disL=dis[0][i],disR=dis[1][prt[i][d]];
- if(prt[i][d]==prt[prd][nd]) disR=0;
- dp[0][i][0][d].set(prd,nd,MIN(disL,disR+2),MIN(disL+1,disR+1));
- dp[0][i][1][d].set(prd,nd,MIN(disR+1,disL+1),MIN(disR,disL+2));
- }
- }
- for(i=1;i<lg;++i){
- for(j=0;j<n;++j){
- dp[i][j][0].resize(prt[j].size());
- dp[i][j][1].resize(prt[j].size());
- for(k=0;k<(int)prt[j].size();++k){
- int d;
- for(d=0;d<2;++d){
- data &trs=dp[i-1][j][d][k],&cur=dp[i][j][d][k];
- if(trs.ld==-1)
- cur.ld=-1;
- else{
- cur=trs;
- cur.tran(dp[i-1][cur.ld][0][cur.rd],dp[i-1][cur.ld][1][cur.rd]);
- }
- }
- }
- }
- }
- while(q--){
- int s[2];
- scanf("%d%d",s,s+1);
- sort(s,s+2);
- int mxl=qrymax(s[0],s[1]),res=inf;
- for(i=mxl;i<=mxl+1;++i){
- data tr[2];
- for(j=0;j<2;++j){
- tr[j]=qrydisV(s[j],i);
- if(tr[j].ld==-1) break;
- }
- if(j<2) break;
- int p[2],d[2];
- for(j=0;j<2;++j){
- p[0]=(j?prt[tr[0].ld][tr[0].rd]:tr[0].ld);
- d[0]=(j?tr[0].rc:tr[0].lc);
- for(k=0;k<2;++k){
- p[1]=(k?prt[tr[1].ld][tr[1].rd]:tr[1].ld);
- d[1]=(k?tr[1].rc:tr[1].lc);
- UMIN(res,d[0]+d[1]+qrydis(p[0],p[1],i));
- }
- }
- }
- printf("%d\n",res-1);
- }
- #ifdef LOCAL
- TReport();
- #endif
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2714185.html