[51nod1502]苹果曼和纸

　　苹果曼有很大的一张纸。这张纸的形状是1×n的长方形。你的任务是帮助苹果曼来折叠这一张纸。有一些操作，这些操作有如下两个种形式：
　　1. 把这张纸在第pi个位置对折。经过对折后，左边的1×pi部分会盖到右边的1×([当前纸片宽度]-pi)上面。
　　2. 询问在如果把距离左端li以内的剪掉，距离左端ri以外的也剪掉，那么还剩下多少纸片的长度。
　　看样例，可以更好的解理这个问题。

　　第一次折叠之后，纸片的宽度变成了4，第二次折叠，纸片的宽度变成了2。

　Input
　　单组测试数据。
　　第一行有两个整数n和q (1≤n≤10^5; 1≤q≤10^5)，表示纸片的宽度和询问数目。
　　接下来q行的形式是如下之一：
　　· "1 pi" (1≤pi<[当前纸片宽度]) — 第一类操作。
　　· "2 li ri" (0≤li<ri≤[当前纸片宽度]) — 第二类操作。
　Output
　　对于第二类操作，输出答案。

　Input示例
　　7 4
　　1 3
　　1 2
　　2 0 1
　　2 1 2
　Output示例
　　4
　　3

　　维护一下每个位置上有多少层纸，每次翻折的时候，只翻较短的一部分（所以得记一下当前的方向），那么总共最多只会有n个位置被翻到别的位置上。

　　主要是记方向、计算实际位置很麻烦...

　　我直接分类讨论。。当前维护的是否是翻转后的、当前翻折操作是否是否会导致翻转，总共四类。

 #include<cstdio>

 #include<iostream>

 #include<cstring>

 #include<algorithm>

 #include<queue>

 #include<cmath>

 #include<cstdlib>

 #define ll long long

 #define ull unsigned long long

 #define ui unsigned int

 //#define d double

 #define ld long double

 const int maxn=,modd=;

 int t[maxn];

 int i,j,k,n,m;

 int ra,fh;char rx;

 inline int read(){

     rx=getchar(),ra=,fh=;

     while(rx<''&&rx!='-')rx=getchar();

     if(rx=='-')fh=-,rx=getchar();

     while(rx>='')ra=ra*+rx-,rx=getchar();return ra*fh;

 }

 inline void add(int x,int V){while(x<=n)t[x]+=V,x+=x&-x;}

 inline int get(int x){

     int sm=,x1=x-;

     while(x)sm+=t[x],x-=x&-x;

     while(x1)sm-=t[x1],x1-=x1&-x1;

     return sm;

 }

 inline int query(int l,int r){

     int sm=;

     while(r)sm+=t[r],r-=r&-r;

     l--;while(l)sm-=t[l],l-=l&-l;return sm;

 }

 int main(){

     n=read(),m=read();register int i,j;

     for(i=;i<=n;i++){t[i]++;if(i+(i&-i)<=n)t[i+(i&-i)]+=t[i];}

     int l,r,stpos=,rest=n,p;bool rev=;

     while(m--){

         if(read()==){

             p=read();

             if((p<<)<=rest)

             if(!rev){

                 for(i=stpos,j=stpos+(p<<)-;i<j;i++,j--)add(j,get(i));

                 stpos+=p;rest-=p;

             }else{

                 for(i=stpos-(p<<)+,j=stpos;i<j;i++,j--)add(i,get(j));

                 stpos-=p;rest-=p;

             }

             else

             if(!rev){

                 p=rest-p;

                 for(i=stpos+rest-,j=i-(p<<)+;j<i;j++,i--)add(j,get(i));

                 rev=,stpos=stpos+rest--p;rest-=p;

             }else{

                 p=rest-p;

                 for(j=stpos-rest+,i=j+(p<<)-;j<i;j++,i--)add(i,get(j));

                 rev=,stpos=stpos-rest++p;rest-=p;

             }

         }else{

             l=read(),r=read()-;

             if(!rev)printf("%d\n",query(stpos+l,stpos+r));

             else printf("%d\n",query(stpos-r,stpos-l));

         }

     //    printf("        rest:%d   st:%d   rev:%d\n",rest,stpos,rev);

     //    for(i=1;i<=rest;i++)printf("  %d",get(stpos+(!rev?i-1:-i+1)));puts("");

     }

 }

巴特西

[51nod1502]苹果曼和纸

最新文章

热门文章