【算法】主席树

【题解】例题，记录和，数字出现超过一半就递归查找。

主席树见

#include
      
       #include
       
        #include
        
         #include
         
          using namespace std;int read(){    char c;int s=0,t=1;    while(!isdigit(c=getchar()))if(c=='-')t=-1;    do{s=s*10+c-'0';}while(isdigit(c=getchar()));    return s*t;}const int maxn=500010;struct tree{
    int l,r,sum;}t[maxn*20];int n,m,sz,root[maxn];void insert(int L,int R,int x,int &y,int v){    y=++sz;    t[y]=t[x];t[y].sum++;    if(L==R)return;    int mid=(L+R)>>1;    if(v<=mid)insert(L,mid,t[x].l,t[y].l,v);    else insert(mid+1,R,t[x].r,t[y].r,v);}int ask(int L,int R,int x,int y,int v){    if(L==R)return L;    else{        int mid=(L+R)>>1;        if(v
          
           >1));    }    return 0;}