[SinGuLaRiTy] 复习模板-数据结构

【SinGuLaRiTy-1040】 Copyright (c) SinGuLaRiTy 2017. All Rights Reserved.

二维线段树 2D_Segment_Tree

//示例：单点修改，区间求和。
//注意内存限制
#include<cstdio>
#include<iostream>
#include<cstring>
const int MAXN = ;
#define L(x) ((x)<<1)
#define R(x) ((x)<<1|1)
#define M(x,y) (((x)+(y))>>1)
using namespace std;
int N, ans;
struct Node {
    short l, r;
    int sum;
} a[MAXN*][MAXN*];
int refer[MAXN];
void build_y(int &xid, int i, short l, short r)
{
    a[xid][i].l = l;
    a[xid][i].r = r;
    if (l == r) return;
    build_y(xid, L(i), l, M(l,r));
    build_y(xid, R(i), M(l,r)+, r);
}
void build_x(int i, short l, short r)
{
    a[][i].l = l;
    a[][i].r = r;
    build_y(i, , , N);
    if (l==r) { refer[l]=i; return; }
    build_x(L(i), l, M(l,r));
    build_x(R(i), M(l,r)+, r);
}

void update(int x, int y, int &dt)
{
    int i = refer[x], j;
    while (i>) {
        j = refer[y];
        while (j>)
            a[i][j].sum += dt, j >>= ;
        i >>= ;
    }
}
void sum_y(int& xid, int i, int& y1, int& y2)
{
    if (a[xid][i].l > y2 || a[xid][i].r < y1)
        return;
    if (a[xid][i].l >= y1 && a[xid][i].r <= y2)
    {
        ans += a[xid][i].sum;
        return;
    }
    sum_y(xid, L(i), y1, y2);
    sum_y(xid, R(i), y1, y2);
}
void sum_x(int i, int& x1, int& y1, int& x2, int& y2)
{
    if (a[][i].l > x2 || a[][i].r < x1)
        return;
    if (a[][i].l >= x1 && a[][i].r <= x2)
    {
        sum_y(i, , y1, y2);
        return;
    }
    sum_x(L(i), x1, y1, x2, y2);
    sum_x(R(i), x1, y1, x2, y2);
}

int main()
{
    int op, x1, y1, x2, y2, t;
    scanf("%d%d", &N, &N);
    build_x(, , N);
    while (scanf("%d", &op) && op!=)
    {
        if (op == )
        {
            scanf("%d%d%d", &x1, &y1, &t);
            update(x1, y1, t);
        }
        else
        {
            scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
            ans = ;
            sum_x(, x1, y1, x2, y2);
            printf("%d\n", ans);
        }
    }
    return ;
}

双向队列 deque

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int MAXN = ;

struct Deque
{
    int nxt[MAXN], prv[MAXN], stk[MAXN], tp;
    int val[MAXN];
    int f, b, size, t;
    void clear() {
        f=b=size=; tp=MAXN-;
        for (int i=; i<MAXN; ++i)
            nxt[i] = prv[i] = , stk[i] = i;
    }
    Deque() { clear(); }
    void push(bool d, int v)
    {
        if (!size) { f = b = stk[tp--]; val[f] = v; prv[f]=nxt[f]=; }
        else {
            t = stk[tp--];
            if (d) { nxt[b] = t; prv[t] = b; nxt[t] = ; val[t] = v; b = t;}
            else { nxt[t] = f; prv[f] = t; prv[t] = ; val[t] = v; f = t; }
        }
        ++size;
    }
    void pop(bool d)
    {
        --size;
        if (d) stk[++tp] = b, b = prv[b];
        else stk[++tp] = f, f = nxt[f];
    }
    int front() { return val[f]; }
    int back() { return val[b]; }
} q;

int main()
{

    return ;
}

Splay平衡树 Splay_Tree

#include<iostream>
#include<cstdio>
#include<cstring>
#define Max(a,b) ((a)>(b)?(a):(b))
#define L(x) x->ch[0]
#define R(x) x->ch[1]
using namespace std;
const int MAXN = ;

struct Node {
    int sz;
    Node *fa, *ch[];
    Node () { sz=; }
}nil, *NIL=&nil;

struct SeqSplay //用来维护区间操作的splay
{
    Node a[MAXN], *root;
    void init() { root=NIL; }
    inline void pushup(Node *x) {
        x->sz = L(x)->sz + R(x)->sz + ;//size域一定要维护

    }
    inline void pushdown(Node *x) {
        //标记下放或者左右交换

    }
    void rotate(Node *x, int d) // 0左1右
    {
        Node *y = x->fa;
        if (y==root) root = x;
        pushdown(y); pushdown(x);
        y->ch[!d] = x->ch[d];
        if (x->ch[d] != NIL)
            x->ch[d]->fa = y;
        x->fa = y->fa;
        if (y->fa != NIL)
            y->fa->ch[ y->fa->ch[]==y ] = x;
        x->ch[d] = y;
        y->fa = x;
        pushup(y); pushup(x);
    }
    void splay(Node*x, Node*target)//双旋至target以下
    {
        Node *y, *z;
        while (x->fa != target) {
            y = x->fa; z = y->fa;
            pushdown(x);
            if (z == target) {
                rotate(x, x==y->ch[]);
                return;
            }
            if (y == L(z))
                if (x == L(y)) rotate(y, ), rotate(x, );
                else rotate(x, ), rotate(x, );
            else
                if (x == R(y)) rotate(y, ), rotate(x, );
                else rotate(x, ), rotate(x, );
            pushup(x);
        }
    }
    Node* build(int l, int r, Node* fa)
    {
        if (l>r) return NIL;
        int mid = (l+r)>>;
        a[mid].ch[] = build(l, mid-, &a[mid]);
        a[mid].ch[] = build(mid+, r, &a[mid]);

        //此处根据题意具体录入节点内容
        pushup(&a[mid]);
        return &a[mid];
    }
    void init(int l, int r) { //伸展树的初始化，外部调用时一定要空置左右端点
        root = build(l, r, NIL);
    }
    void getkth(int k, Node *&target)//将第k个元素旋转至target下面
    {
        Node *t = root;
        while () {
            pushdown(t);
            if (k == (t->ch[]->sz)+) {
                splay(t, target);
                return;
            }
            if (k <= L(t)->sz) t = L(t);
            else k-=L(t)->sz+, t = R(t);
        }
    }
    void form(int l, int r) //将区间[l,r]旋转至操作区域
    {
        getkth(l, root);
        getkth(r+, R(root));
    }

} tree;

int main()
{

    return ;
}

线段树

struct node
{
    int l ,r ,sum ;
}tre[MAXN<<] ;

void build(int code,int l,int r)
{
    tre[code].l=l ,tre[code].r=r ;
    if(l==r)return;
    build(code*,l,(l+r)/);
    build(code*+,(l+r)/+,r);
}

void update(int code,int l,int r)
{
    if(l<=tre[code].l&&tre[code].r<=r)
    {
        //修改
        return;
    }
    //若有懒标记 pushdown();
    int mid=(tre[code].l+tre[code].r)/;
    if(l<=mid)update(code*,l,r);
    if(mid<r)update(code*+,l,r);
    //更新 pushup();
    tre[code].sum=tre[code*].sum+tre[code*+].sum;
}

int query(int code,int l,int r)
{
    if(l<=tre[code].l&&tre[code].r<=r)
        return tre[code].sum;
    int mid=(tre[code].l+tre[code].r)/ ,ans= ;
    //pushdown();
    if(l<=mid)ans+=query(code*,l,r);
    if(mid<r)ans+=query(code*+,l,r);
    return ans;
}

二维树状数组

#define LL long long int
#define lowbit(a) ((a)&(-(a)))
LL tre[MAXN+][MAXN+] ;
void update(int a,int b,LL val)
{
    val%=mod;
    for(;a<=n;a+=lowbit(a))
        for(int j=y;j<=m;j+=lowbit(j))
        {
            tre[i][j]+=val;
            if(tre[a][j]>=mod)tre[a][j]-=mod;
        }
}

LL getsum(int x,int y)
{
    LL ans=;
    for(;x>;x-=lowbit(x))
        for(int j=y;j>;j-=lowbit(j))
        {
            ans+=tre[x][j];
            if(ans>=mod)ans-=mod;
        }
    return ans;
}

树状数组

#define lowbit(a) ((a)&(-(a)))
#define LL long long int
LL tre[MAXN+] ;
void update(LL a,int pos)
{
    a%=mod;
    while(pos<=n)
    {
        tre[pos]+=a;
        if(tre[pos]>=mod)tre[pos]-=mod;
        pos+=lowbit(pos);
    }
}

LL getsum(int pos)
{
    LL ans= ;
    while(pos>)
    {
        ans+=tre[pos];
        if(ans>=mod)ans-=mod;
        pos-=lowbit(pos);
    }
    return ans;
}

并查集

int getroot(int a)
{
    if(fa[a]==a)return a;
    return fa[a]=getroot(fa[a]);
}

void Union(int a,int b)
{
    fa[getroot(a)]=getroot(b);
}

归并排序

///归并排序模板。记得和快排一块对着看。
#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<cstring>
#include<cstring>
#include<string>
#include<cmath>
#include<algorithm>
#define LL long long
#define inf 0x3f3f3f3f
#define mod 1e9+7
const int maxn=1e5+;
using namespace std;
int temp[maxn];
int num=;///统计逆序对数的。
void Merge(int a[],int left ,int mid,int right)
{
    int i=left,j=mid+,n=,length=right-left;///i开始为左半部分最左边，j为右半部分最左边。temp数组是从下标0开始存数。
    while(i<=mid&&j<=right){
        if(a[i]>a[j]){///左边比右边大。
            temp[n++]=a[j++];
            num+=mid-i+;///从i到mid都是比a[j]大。
        }
        else{
            temp[n++]=a[i++];
        }
    }
    if(i>mid){///这里说明的是左边全部填满了(因为前面的判断条件是i<=mid，那就是天右边了。
        while(j<=right){
            temp[n++]=a[j++];
        }
    }
    else{
        while(i<=mid){
            temp[n++]=a[i++];
        }
    }
    for(int k=;k<=length;k++){///最后赋值到原数组必须要有的。
        a[left+k]=temp[k];
    }
}
void mergesort(int a[],int left,int right)
{
    if(left<right){
        int mid=(left+right)/;
        mergesort(a,left,mid);
        mergesort(a,mid+,right);
        Merge(a,left,mid,right);
    }
}
int main()
{
    int number[] = {};
    mergesort(number,,-);///初始化调用也要注意额。

    for(int i=;i<;i++){
        printf("%d ",number[i]);
    }
}

堆排序

int adjust_heap(vector<int> &v, int length, int i){
        int left =  * i;
        int right =  * i + ;
        int largest = i;
        int temp;

        while(left < length || right < length){
                if (left < length && v[largest] < v[left]){
                        largest = left;
                }
                if (right < length && v[largest] < v[right]){
                        largest = right;
                }

                if (i != largest){
                        temp = v[largest];
                        v[largest] = v[i];
                        v[i] = temp;
                        i = largest;
                        left =  * i;
                        right =  * i + ;
                }
                else{
                        break;
                }
        }
}

int build_heap(vector<int> &v, int length){
        int i;
        int begin = length/ - ; //get the last parent node
        for (i = begin; i>=; i--){
                adjust_heap(v,length,i);
        }
}

int heap_sort(vector<int> &v){
        int length = v.size();
        int temp;
        printline("before sort:",v);
        build_heap(v,length);
        while(length > ){
                temp = v[length-];
                v[length-] = v[];
                v[] = temp;
                length--;
                adjust_heap(v,length,);
        }
        printline("after sort:",v);
}

线段树(update:单点增减; query:区间求和) - HDU1166 敌兵布阵

#include <cstdio>

#define lson l , m , rt << 1
#define rson m + 1 , r , rt << 1 | 1
const int maxn = ;
int sum[maxn<<];
void PushUP(int rt) {
       sum[rt] = sum[rt<<] + sum[rt<<|];
}
void build(int l,int r,int rt) {
       if (l == r) {
              scanf("%d",&sum[rt]);
              return ;
       }
       int m = (l + r) >> ;
       build(lson);
       build(rson);
       PushUP(rt);
}
void update(int p,int add,int l,int r,int rt) {
       if (l == r) {
              sum[rt] += add;
              return ;
       }
       int m = (l + r) >> ;
       if (p <= m) update(p , add , lson);
       else update(p , add , rson);
       PushUP(rt);
}
int query(int L,int R,int l,int r,int rt) {
       if (L <= l && r <= R) {
              return sum[rt];
       }
       int m = (l + r) >> ;
       int ret = ;
       if (L <= m) ret += query(L , R , lson);
       if (R > m) ret += query(L , R , rson);
       return ret;
}
int main() {
       int T , n;
       scanf("%d",&T);
       for (int cas =  ; cas <= T ; cas ++) {
              printf("Case %d:\n",cas);
              scanf("%d",&n);
              build( , n , );
              char op[];
              while (scanf("%s",op)) {
                     if (op[] == 'E') break;
                     int a , b;
                     scanf("%d%d",&a,&b);
                     if (op[] == 'Q') printf("%d\n",query(a , b ,  , n , ));
                     else if (op[] == 'S') update(a , -b ,  , n , );
                     else update(a , b ,  , n , );
              }
       }
       return ;
}

树的点分治-找出树中有多少点对,满足dis(u,k)<K

#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<vector>
#include<cmath>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<algorithm>
using namespace std;
const int maxn=;
int N,K;
int ans,root,Max;
struct node
{
    int v,next,w;
}edge[maxn*];
int head[maxn],tot;
int size[maxn];//树的大小
int maxv[maxn];//最大孩子节点的size
int vis[maxn];
int dis[maxn];
int num;
void init()
{
    tot=;
    ans=;
    memset(head,-,sizeof(head));
    memset(vis,,sizeof(vis));
}
void add_edge(int u,int v,int w)
{
    edge[tot].v=v;
    edge[tot].w=w;
    edge[tot].next=head[u];
    head[u]=tot++;
}
//处理子树的大小
void dfssize(int u,int f)
{
    size[u]=;
    maxv[u]=;
    for(int i=head[u];i!=-;i=edge[i].next)
    {
        int v=edge[i].v;
        if(v==f||vis[v])continue;
        dfssize(v,u);
        size[u]+=size[v];
        if(size[v]>maxv[u])maxv[u]=size[v];
    }
}
//找重心
void dfsroot(int r,int u,int f)
{
    if(size[r]-size[u]>maxv[u])//size[r]-size[u]是u上面部分的树的尺寸，跟u的最大孩子比，找到最大孩子的最小差值节点
        maxv[u]=size[r]-size[u];
    if(maxv[u]<Max)Max=maxv[u],root=u;
    for(int i=head[u];i!=-;i=edge[i].next)
    {
        int v=edge[i].v;
        if(v==f||vis[v])continue;
        dfsroot(r,v,u);
    }
}
//求每个点离重心的距离
void dfsdis(int u,int d,int f)
{
    dis[num++]=d;
    for(int i=head[u];i!=-;i=edge[i].next)
    {
        int v=edge[i].v;
        if(v!=f&&!vis[v])
            dfsdis(v,d+edge[i].w,u);
    }
}
//计算以u为根的子树中有多少点对的距离小于等于K
int calc(int u,int d)
{
    int ret=;
    num=;
    dfsdis(u,d,);
    sort(dis,dis+num);
    int i=,j=num-;
    while(i<j)
    {
        while(dis[i]+dis[j]>K&&i<j)j--;
        ret+=j-i;
        i++;
    }
    return ret;
}
void dfs(int u)
{
    Max=N;
    dfssize(u,);
    dfsroot(u,u,);
    ans+=calc(root,);
    vis[root]=;
    for(int i=head[root];i!=-;i=edge[i].next)
    {
        int v=edge[i].v;
        if(!vis[v])
        {
            ans-=calc(v,edge[i].w);
            dfs(v);
        }
    }
}
int main()
{
    while(scanf("%d%d",&N,&K)!=EOF)
    {
        if(!N&&!K)break;
        int u,v,w;
        init();
        for(int i=;i<N;i++)
        {
            scanf("%d%d%d",&u,&v,&w);
            add_edge(u,v,w);
            add_edge(v,u,w);
        }

        dfs();
        printf("%d\n",ans);
    }
    return ;
}

Lower_bound & Upper_bound

ForwardIterator my_lower_bound(ForwardIterator beg, ForwardIterator end, T target)
{
    ForwardIterator mid;
    typename iterator_traits<ForwardIterator>::difference_type count, step;

    count = distance(beg, end);
    while(count > )
    {
        mid = beg;
        step = count/;
        advance(mid, step);
        if(*mid < target) //mid < target
        {
            beg = ++mid;
            count -= (step+); //count表示当前数组中还有的元素个数
        }
        else
        {
            count = step;
        }
    }
    return beg;
}

template<class ForwardIterator, class T>
ForwardIterator my_upper_bound(ForwardIterator beg, ForwardIterator end, T target)
{
    ForwardIterator mid;
    typename iterator_traits<ForwardIterator>::difference_type count, step;

    count = distance(beg, end);
    while(count > )
    {
        mid = beg;
        step = count/;
        advance(mid, step);
        if(target < *mid) //mid < target
        {
            count = step;
        }
        else
        {
            beg = ++mid;
            count -= (step+);
        }
    }
    return beg;
}

二分查找

//递归版本
int  binarySearchRecusion(int* array,int len,int value){
    if(len==)
        return -;

    int mid=(len-)/;
    if(array[mid]==value)
        return mid;
    if(array[mid]>value)                        //在右半区
        binarySearchRecusion(array+mid+,len-mid-,value);
    else
        binarySearchRecusion(array,mid,value);  //在左半区
}

//非递归版本
//有序数组递减排列
int  binarySearch(int* array,int len,int value){
    int mid=;
    int low=;
    int high=len-;
    while(low<=high){
        mid=(low+high)/;
        if(array[mid]>value){       //在右半区
            low=mid+;
            continue;
        }
        else if(array[mid]<value){  //在左半区
            high=mid-;
            continue;
        }else
            return mid;             //找到
    }
    return -;   //查找失败
}

三分查找

double solve(double MIN,double MAX)
{
    double Left, Right;
    double mid, midmid;
    double mid_value, midmid_value;
    Left = MIN;
    Right = MAX;
    while (Left +eps < Right)
    {
        mid = (Left + Right) / ;
        midmid = (mid + Right) / ;
        mid_value = Calc(mid); //Cal()为题意规定的计算内容
        midmid_value = Calc(midmid);
        ///求最大值改成>= 最小值改成<=
        if (mid_value >= midmid_value) Right = midmid;
        else Left = mid;
    }
    return Left;
}

Time: 2017-10-17