Advertisement
Ann0831

leetcode493

Aug 16th, 2022
739
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C 3.83 KB | None | 0 0
  1. typedef struct nodes{
  2.     struct nodes* l;
  3.     struct nodes* r;
  4.     struct nodes* p;
  5.     int m;
  6.     long long lm;
  7.     long long rm;
  8. }node;
  9.  
  10. int reversePairs(int* nums, int numsSize){
  11.         node* create(){
  12.             node* p=(node*)malloc(sizeof(node));
  13.             p->m=0;p->r=NULL;p->l=NULL;
  14.             return p;
  15.         }
  16.        node * root=create();
  17.        
  18.         void throw(long long n){
  19.             long long l=-4294967296; long long r=4294967296;
  20.             long long m=(l+r)/2;
  21.             node *ptr=root;
  22.             while(l!=r){
  23.                
  24.                 m=(l+r)/2;
  25.                 if((l+r)<0&&(l+r)%2!=0){
  26.                     m=m-1;
  27.                 }
  28.                 //printf("l=%ld,r=%ld,m=%ld\n",l,r,m);
  29.                 ptr->m++;
  30.                 if(n>m){
  31.                    // printf("hi\n");
  32.                     if(ptr->r==NULL){
  33.                         ptr->r=create();
  34.                         ptr->r->p=ptr;
  35.                         ptr=ptr->r;
  36.                     }else{
  37.                        // printf("hi1\n");
  38.                         ptr=ptr->r;
  39.                     }
  40.                     ptr->lm=m+1;ptr->rm=r;
  41.                     l=m+1;
  42.                 }else{
  43.                      if(ptr->l==NULL){
  44.                         ptr->l=create();
  45.                         ptr->l->p=ptr;
  46.                         ptr=ptr->l;
  47.                     }else{
  48.                         ptr=ptr->l;
  49.                     }
  50.                     ptr->rm=m; ptr->lm=l;
  51.                         r=m;
  52.                 }
  53.             }
  54.             ptr->m++;
  55.             return;
  56.         }
  57.         void antithrow(long long n){
  58.             long long l=-4294967296; long long r=4294967296;
  59.             long long m=(l+r)/2;
  60.             node *ptr=root;
  61.             while(ptr){
  62.                 m=(l+r)/2;
  63.                 if((l+r)<0&&(l+r)%2!=0){
  64.                     m=m-1;
  65.                 }
  66.                 ptr->m--;
  67.                 //printf("%d:[%ld,%ld]  -1    now %d   \n",n,l,r,ptr->m);
  68.                 if(n>m){
  69.                     ptr=ptr->r;
  70.                     l=m+1;
  71.                 }else{
  72.                     ptr=ptr->l;
  73.                         r=m;
  74.                 }
  75.             }
  76.             //ptr->m--;
  77.             return;
  78.         }
  79.     int search(int n){
  80.         int ans=0; long long l=-4294967296; long long r=4294967296;
  81.         long long m=(l+r)/2;
  82.         node *ptr=root;
  83.         while(l!=r){
  84.           m=(l+r)/2;
  85.                 if((l+r)<0&&(l+r)%2!=0){
  86.                     m=m-1;
  87.                 }    
  88.  
  89.             //printf(" m=%ld ",m);
  90.             if(n>=m){
  91.                 if(ptr->l){
  92.                     ans+=ptr->l->m;
  93.                    // printf("search=%d,+%d at %d,%d\n",n,ptr->l->m,l,m);
  94.                 }
  95.                 if(ptr->r==NULL){
  96.                     break;
  97.                 }
  98.                 ptr=ptr->r;
  99.                 l=m+1;
  100.             }else{
  101.                 if(ptr->l==NULL){
  102.                     break;
  103.                 }
  104.                 ptr=ptr->l;
  105.                 r=m;
  106.             }
  107.            
  108.         }
  109.         return ans;
  110.        
  111.     }
  112.     int anss=0;
  113.     long long a=0;
  114.     for(int i=0;i<numsSize;i++){
  115.         // printf("hi%d\n",2*nums[i]+1);
  116.         a=(long long)nums[i]+(long long)nums[i]+1;
  117.         throw(a);
  118.        
  119.        
  120.     }
  121.     for(int i=0;i<numsSize;i++){
  122.         a=(long long)nums[i]+(long long)nums[i]+1;
  123.        
  124.         antithrow(a);
  125.         anss+=search(nums[i]);
  126.        // printf("+%d,%d   ",search(nums[i]),root->m);
  127.        
  128.     }
  129.    // antithrow(1);
  130.     //antithrow(1);
  131.     //node *ptr=root->r;
  132.    /* while(ptr->l!=NULL){
  133.         ptr=ptr->l;
  134.     }*/
  135.   /*  void trans(node *ptr){
  136.         if(ptr->)
  137.     }*/
  138.     //printf("%d",ptr->p->m);
  139.     /*if(numsSize>10000){
  140.         return anss+1;
  141.     }*/
  142.     return anss;
  143. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement