每日一题 day4 打卡

Analysis

暴力+快排（其实是归并排序）

一开始天真的以为sort能过，结果光荣TLE，由于每次只更改相邻的元素，于是善于处理随机数的快排就会浪费很多时间。于是就想到归并排序：归并排序的思想就是合

并两个同序数组的线性方式——每次比较两个有序数组指针指向的值，谁更小（大）则放到temp数组里，然后删掉进入temp的元素，指针++。然而我并没有实现，先把

快排水过的代码放上来，等有时间学归并排序了再来改。

1 #pragma GCC optimize(2) 2 #include
     
       3 #include
      
        4 #include
       
         5 #include
        
          6 #define maxn 100000+10 7 using namespace std; 8 inline int read()  9 {10     int x=0;11     bool f=1;12     char c=getchar();13     for(; !isdigit(c); c=getchar()) if(c=='-') f=0;14     for(; isdigit(c); c=getchar()) x=(x<<3)+(x<<1)+c-'0';15     if(f) return x;16     return 0-x;17 }18 inline void write(int x)19 {20     if(x<0){putchar('-');x=-x;}21     if(x>9)write(x/10);22     putchar(x%10+'0');23 }24 int n,r,q; 25 struct node 26 {27     int num,s,w;28 }x[2*maxn];29 inline bool cmp(node a,node b)30 {31     if(a.s!=b.s) return a.s>b.s;32     else return a.num
         
          x[i-1].w) x[i].s+=1;45             else if(x[i].w
         
        
       
      
     

请各位大佬斧正（反正我不认识斧正是什么意思）