数据结构总结

• 堆（优先队列）

　　

 

　　开一个大根堆，一个小根堆，保证大根堆的元素个数为查询的i-1，输出小根堆的堆顶即可。如果插入的数a[j]比大根堆堆顶小，则把大根堆堆顶放到小根堆，a[j]放到大根堆里，保证大根堆里的最大值小于小根堆里的最小值。查询时把小根堆的堆顶放到大根堆里，使大根堆元素个数+1。

code：

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          using namespace std;const int N=200010;priority_queue
          
           qmax;priority_queue
           
            
             ,greater
             
               >qmin;int m,n;int a[N],u[N];int main(){ scanf("%d%d",&m,&n); int j=0; for(int i=1;i<=m;i++)scanf("%d",&a[i]); for(int i=1;i<=n;i++)scanf("%d",&u[i]); for(int i=1;i<=n;i++) { while(j
              
               qmax.top()) { qmin.push(a[j]); } if(qmax.size()&&a[j]
              
             
            
           
          
         
        
       
      
     

• 线段树

　　

　　直接做会觉得无从下手，我们考虑二分一个排名k，把比k小的数变成0，>=k的变成1，这样判断查找的pos值是0还是1，如果是1，说明二分的排名小了，否则说明排名大了，check用线段树维护区间1的个数，并支持覆盖（染色）和查询操作。

code:

#include
     
      #include
      
       #include
       
        #include
        
         #define lch (now<<1)#define rch (now<<1|1)#define smid  ((l+r)>>1)using namespace std;const int N=1e5+10;struct node{    int l,r,cover,sum;}sgt[N<<2];int n,m,pos;int b[N];struct Q{    int cid,l,r;}q[N];void pushup(int now){    sgt[now].sum=sgt[lch].sum+sgt[rch].sum;}    void bt(int now,int l,int r,int x){    sgt[now].cover=-1;    if(l==r)    {        sgt[now].sum=b[l]>=x;return;    }    bt(lch,l,smid,x);    bt(rch,smid+1,r,x);    pushup(now);}void pushdown(int now,int l,int r){    if(sgt[now].cover==-1)return;    sgt[lch].cover=sgt[rch].cover=sgt[now].cover;    if(sgt[now].cover==1)sgt[lch].sum=(smid-l+1),sgt[rch].sum=(r-smid);    else sgt[lch].sum=sgt[rch].sum=0;    sgt[now].cover=-1;}int query(int now,int l,int r,int x,int y){    if(x<=l&&r<=y)return sgt[now].sum;    if(x>r||y
         
          r||y
          
           >1); if(check(mid))L=mid; else R=mid; } printf("%d",L);}
          
         
        
       
      
     

• 树状数组（Binary Indexed Tree）

　　

　　

#include
     
      #include
      
       #include
       
        #include
        
         #define go(i,a,b) for(int i=a;i<=b;i++)#define lowbit(x) (x&-x)#define LL long long using namespace std;const int N=20010;struct COW{    int v,x;}c[N];int n;LL tot,ans;LL bit1[N],bit2[N];bool cmp(COW a,COW b){    return a.v
        
       
      
     

•  并查集

　　

　　merge和find操作没什么不同。难点在删除操作。

　　我们给0->n-1的每个点的父亲赋为n->n*2-1，相当于一个虚拟父亲。这样我们在0->n-1元素中合并时，根节点始终在n->n*2-1，我们在从并查集中删除节点时，直接把其父亲赋为n*2->m中的元素，这样和它在同一个集合里的元素根在n->n*2-1中，它可以直接删除。

code:

#include
     
      #include
      
       #include
       
        #include
        
         using namespace std;const int N=1e5+10;const int M=1e6+10;int father[2*N+M];bool vis[2*N+M];int n,m,tmp;int find(int x){    if(x==father[x])return  x;    return father[x]=find(father[x]);}int main(){    int T=0;    while(1)    {        scanf("%d%d",&n,&m);        if(!n&&!m)return 0;        tmp=n<<1;T++;        for(int i=0;i
         
          >opt;            if(opt=='M')            {                int x,y;scanf("%d%d",&x,&y);                int r1=find(x),r2=find(y);                father[r1]=r2;            }            if(opt=='S')            {                int x;scanf("%d",&x);                father[x]=tmp++;            }        }int ans=0;        for(int i=0;i