tips

不知道为什么，明明代码是错的应该，但是还是过了？？？

AC代码

#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
const int maxc = 10000 + 5, maxn = 300000 + 5;
int n,c,m;
int rt[maxn],cnt;
 
struct node {
    int sum,ls,rs;
}nod[maxn * 25];
 
void update(int l,int r,int &x,int y,int k){
    nod[++cnt] = nod[y];nod[cnt].sum++;x = cnt;
    if(l == r)return;
    int mid = (l + r) >> 1;
    if(k <= mid)update(l,mid,nod[x].ls,nod[y].ls,k);
    else update(mid + 1,r,nod[x].rs,nod[y].rs,k);
}
 
int query(int l,int r,int x,int y,int k){
    if(l == r)return l;
    int mid = (l + r) >> 1;
    if((nod[nod[y].ls].sum - nod[nod[x].ls].sum) * 2 > k)return query(l,mid,nod[x].ls,nod[y].ls,k);
    if((nod[nod[y].rs].sum - nod[nod[x].rs].sum) * 2 > k)return query(mid+1,r,nod[x].rs,nod[y].rs,k);
    return 0;
}
 
int ask(int l, int r, int x, int y, int k) {
  if (l == r) return nod[y].sum - nod[x].sum;
  int mid = l + r >> 1;
  if (k <= mid) return ask(l, mid, nod[x].ls, nod[y].ls, k);
  else return ask(mid+1, r, nod[x].rs, nod[y].rs, k);  
}
 
int main(){
    scanf("%d %d",&n,&m);
    c = (int)3e5;
    for(int i = 1;i <= n;i++){
        int x;scanf("%d",&x);
        update(1,c,rt[i],rt[i-1],x);
    }
//    int m;scanf("%d",&m);
    for(int i = 1;i <= m;i++){
        int x,y;scanf("%d %d",&x,&y);
        int ans = query(1,c,rt[x-1],rt[y],y-x+1);
        int len = y - x + 1;
        if (ans == 0) puts("1");
        else {
          int res = ask(1, c, rt[x-1], rt[y], ans);
          printf("%d\n",abs(res - (len - res)));
        }
    }
    return 0;
}

主席树求区间众数

原文：https://www.cnblogs.com/www208/p/14679650.html