deadwing97

PERMLIST Author

Feb 24th, 2019
98
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <algorithm>
  3. #include <string>
  4. #include <assert.h>
  5. using namespace std;
  6.  
  7.  
  8.  
  9. long long readInt(long long l,long long r,char endd){
  10.     long long x=0;
  11.     int cnt=0;
  12.     int fi=-1;
  13.     bool is_neg=false;
  14.     while(true){
  15.         char g=getchar();
  16.         if(g=='-'){
  17.             assert(fi==-1);
  18.             is_neg=true;
  19.             continue;
  20.         }
  21.         if('0'<=g && g<='9'){
  22.             x*=10;
  23.             x+=g-'0';
  24.             if(cnt==0){
  25.                 fi=g-'0';
  26.             }
  27.             cnt++;
  28.             assert(fi!=0 || cnt==1);
  29.             assert(fi!=0 || is_neg==false);
  30.            
  31.             assert(!(cnt>19 || ( cnt==19 && fi>1) ));
  32.         } else if(g==endd){
  33.             assert(cnt>0);
  34.             if(is_neg){
  35.                 x= -x;
  36.             }
  37.             assert(l<=x && x<=r);
  38.             return x;
  39.         } else {
  40.             assert(false);
  41.         }
  42.     }
  43. }
  44. string readString(int l,int r,char endd){
  45.     string ret="";
  46.     int cnt=0;
  47.     while(true){
  48.         char g=getchar();
  49.         assert(g!=-1);
  50.         if(g==endd){
  51.             break;
  52.         }
  53.         cnt++;
  54.         ret+=g;
  55.     }
  56.     assert(l<=cnt && cnt<=r);
  57.     return ret;
  58. }
  59. long long readIntSp(long long l,long long r){
  60.     return readInt(l,r,' ');
  61. }
  62. long long readIntLn(long long l,long long r){
  63.     return readInt(l,r,'\n');
  64. }
  65. string readStringLn(int l,int r){
  66.     return readString(l,r,'\n');
  67. }
  68. string readStringSp(int l,int r){
  69.     return readString(l,r,' ');
  70. }
  71.  
  72. int T;
  73. int n;
  74. int sm_n=0;
  75. int p[1001001];
  76. int pos[1001001];
  77. bool vis[1001001];
  78.  
  79. int ii[1001001];
  80. int jj[1001001];
  81. int op[1001001];
  82. int m=0;
  83. bool ok=true;
  84.  
  85. int solve(int l,int r,int low,int up){
  86.     if(l==r){
  87.         return 1;
  88.     }
  89.     if(pos[low] < pos[up] ){
  90.         int ll=l,rr=r;
  91.  
  92.         int mx_l=-1<<30;
  93.         int mn_r= 1<<30;
  94.         int mid=-1;
  95.         while(ll<rr){
  96.             mx_l=max(mx_l,p[ll]);
  97.             if(ll- l == mx_l - low ){
  98.                 mid = ll;
  99.                 break;
  100.             }
  101.             ll++;
  102.             mn_r = min(mn_r,p[rr]);
  103.             if(r-rr == up - mn_r){
  104.                 mid = rr-1;
  105.                 break;
  106.             }
  107.             rr--;
  108.         }
  109.         if(mid == -1){
  110.             ok=false;
  111.             return -1;
  112.         }
  113.         int _i = solve(l,mid,low,low + mid - l);
  114.         int _j = solve(mid+1,r,up - (r-mid-1),up);
  115.         ii[m] = _i;
  116.         jj[m] = _j;
  117.         op[m] = 1;
  118.         m++;
  119.         return m-1;
  120.     } else {
  121.         int ll=l,rr=r;
  122.  
  123.         int mn_l=1<<30;
  124.         int mx_r=-1<<30;
  125.         int mid=-1;
  126.         while(ll<rr){
  127.             mn_l=min(mn_l,p[ll]);
  128.             if(ll- l == up - mn_l ){
  129.                 mid = ll;
  130.                 break;
  131.             }
  132.             ll++;
  133.             mx_r = max(mx_r,p[rr]);
  134.             if(r-rr == mx_r - low){
  135.                 mid = rr-1;
  136.                 break;
  137.             }
  138.             rr--;
  139.         }
  140.         if(mid == -1){
  141.             ok=false;
  142.             return -1;
  143.         }
  144.         int _i = solve(l,mid,up - (mid-l),up);
  145.         int _j = solve(mid+1,r,low,low + (r - mid-1));
  146.         ii[m] = _i;
  147.         jj[m] = _j;
  148.         op[m] = 2;
  149.         m++;
  150.         return m-1;
  151.     }
  152. }
  153. int main(){
  154.     //freopen("07.txt","r",stdin);
  155.     //freopen("07oo.txt","w",stdout);
  156.     T=readIntLn(1,1000);
  157.     while(T--){
  158.         n=readIntLn(2,1000000);
  159.         sm_n +=n ;
  160.         assert(sm_n<=1000000);
  161.         for(int i=1;i<=n;i++){
  162.             vis[i]=false;
  163.         }
  164.         m=2;
  165.         ok=true;
  166.         for(int i=1;i<=n;i++){
  167.             if(i==n){
  168.                 p[i]=readIntLn(1,n);
  169.             } else {
  170.                 p[i]=readIntSp(1,n);
  171.             }
  172.             pos[p[i]]=i;
  173.             assert(vis[p[i]]==false);
  174.             vis[p[i]]=true;
  175.         }
  176.         solve(1,n,1,n);
  177.         if(!ok){
  178.             //cout<<"NO"<<endl;
  179.             printf("NO\n");
  180.         } else {
  181.             //cout<<"YES"<<endl;
  182.             printf("YES\n");
  183.             //cout<<m-2<<endl;
  184.             printf("%d\n",m-2);
  185.             for(int i=2;i<m;i++){
  186.                 printf("%d %d %d\n",ii[i],jj[i],op[i]);
  187.                 //cout<<ii[i]<< " "<<jj[i]<<" "<<op[i]<<endl;
  188.             }
  189.         }
  190.        
  191.     }
  192.     assert(getchar()==-1);
  193. }
RAW Paste Data