题解

42 条题解

  • 1
    @ 2016-08-21 15:54:54

    我知道ls想让我写一个树套树,可是。。
    用O(n)的kth算法可以AC为什么写树套树呢?
    ```c++
    测试数据 #0: Accepted, time = 250 ms, mem = 948 KiB, score = 10
    测试数据 #1: Accepted, time = 500 ms, mem = 948 KiB, score = 10
    测试数据 #2: Accepted, time = 46 ms, mem = 952 KiB, score = 10
    测试数据 #3: Accepted, time = 312 ms, mem = 948 KiB, score = 10
    测试数据 #4: Accepted, time = 156 ms, mem = 948 KiB, score = 10
    测试数据 #5: Accepted, time = 500 ms, mem = 952 KiB, score = 10
    测试数据 #6: Accepted, time = 515 ms, mem = 948 KiB, score = 10
    测试数据 #7: Accepted, time = 531 ms, mem = 948 KiB, score = 10
    测试数据 #8: Accepted, time = 656 ms, mem = 952 KiB, score = 10
    测试数据 #9: Accepted, time = 109 ms, mem = 952 KiB, score = 10

    Accepted, time = 3575 ms, mem = 952 KiB, score = 100

    c++
    #include <bits/stdc++.h>
    using namespace std;

    int n, q, t;
    char c;
    int arr[50005], a[50005];

    int read()
    {
    int a = 0, c;
    do c = getchar(); while (!isdigit(c));
    while (isdigit(c)) {
    a = a*10+c-'0';
    c = getchar();
    }
    return a;
    }

    char get()
    {
    char c;
    while (!isalpha(c))
    c = getchar();
    return c;
    }

    int kth(int l, int r, int k)
    {
    for (int i = l; i <= r; i++) arr[i] = a[i];
    while (1) {
    //cout << l << " " << r << " " << k << endl;
    if (l == r) return arr[l];
    swap(arr[l], arr[(l+r)>>1]);
    int m = l;
    for (int i = l+1; i <= r; i++)
    if (arr[i] < arr[l])
    swap(arr[++m], arr[i]);
    swap(arr[l], arr[m]);
    // cout << l << " " << r << " " << k << " " << m << endl;
    if (k == m) return arr[k];
    else if (k <= m) r = m-1;
    else l = m+1;
    }
    }
    int main()
    {
    n = read(); q = read();
    for (int i = 1; i <= n; i++)
    a[i] = read();
    for (int i = 1; i <= q; i++) {
    c = get();
    int a1, b, d;
    if (c == 'Q') {
    a1 = read(); b = read(); d = read();
    if (b < a1) swap(a1, b);
    printf("%d\n", kth(a1, b, a1+d-1));
    } else {
    a1 = read(); b = read();
    a[a1] = b;
    }
    }
    return 0;
    }

    • @ 2016-08-21 15:56:22

      70行水过,顺便:
      Orz会树套树的犇们

    • @ 2016-08-21 16:54:58

      你这方法真666。。。

    • @ 2016-08-26 17:05:38

      暴力出奇迹,是OI界永恒不变的真理

  • 0
    @ 2018-08-17 07:45:13

    Markdown

  • 0
    @ 2017-07-03 18:45:37
    #include <bits/stdc++.h>
    
    using namespace std;
    const int N = 50010;
    typedef unsigned long ul;
    typedef int seg[90 * N];
    typedef int arr[N];
    typedef pair<int, int> pii;
    seg lson, rson, c;
    arr a, bit;
    vector<int> x;
    int tot, n, m, xsiz;
    
    struct T {
        int p, val, l, r;
        char t;
    } q[N];
    
    void init_hash() {
        sort(x.begin(), x.end());
        auto en = unique(x.begin(), x.end());
        xsiz = (int) (en - x.begin());
        x.resize((ul) xsiz);
    }
    
    int hafn(int val) {
        return (int) (lower_bound(x.begin(), x.end(), val) - x.begin()) + 1;
    }
    
    int lowbit(int x) {
        return x & -x;
    }
    
    void segins(int &i, int l, int r, int p, int del) {
        if (i == 0)
            i = [&tot]() {
                int res = ++tot;
                lson[res] = rson[res] = c[res] = 0;
                return res;
            }();
        c[i] += del;
        if (l == r) return;
        int mid = l + r >> 1;
        if (p <= mid) segins(lson[i], l, mid, p, del);
        else segins(rson[i], mid + 1, r, p, del);
    }
    
    void bitchg(int p, int val, int del) {
        while (p <= n) {
            segins(bit[p], 1, xsiz, val, del);
            p += lowbit(p);
        }
    }
    
    int bitask(int l, int r, int k) {
        vector<pii> v;
        auto f = [&v](int x, int del) {
            while (x) {
                v.push_back(pii(bit[x], del));
                x -= lowbit(x);
            }
        };
        auto turn = [&v](int dir) {
            transform(v.begin(), v.end(), v.begin(), [dir](pii x) -> pii {
                return dir ? pii(rson[x.first], x.second) : pii(lson[x.first], x.second);
            });
        };
        auto getleft = [&v]() {
            int tot = 0;
            for_each(v.begin(), v.end(), [&tot](pii x) { tot += c[lson[x.first]] * x.second; });
            return tot;
        };
        f(l - 1, -1);
        f(r, 1);
        l = 1;
        r = xsiz;
        while (l < r) {
            int mid = l + r >> 1, tmp = getleft();
            if (k <= tmp) {
                r = mid;
                turn(0);
            } else {
                l = mid + 1;
                k = k - tmp;
                turn(1);
            }
        }
        return l;
    }
    
    int main() {
        //int t;
        //cin >> t;
        //while (t--) {
            x.clear();
            tot = 0;
            cin >> n >> m;
            memset(bit, 0, sizeof(int) * (n + 1));
            for (int i = 1; i <= n; i++) scanf("%d", a + i), x.push_back(a[i]);
            for (int i = 1; i <= m; i++) {
                getchar();
                q[i].t = (char) getchar();
                if (q[i].t == 'C') {
                    scanf("%d%d", &q[i].p, &q[i].val);
                    x.push_back(q[i].val);
                } else scanf("%d%d%d", &q[i].l, &q[i].r, &q[i].val);
            }
            init_hash();
            transform(a + 1, a + n + 1, a + 1, [](int x) { return hafn(x); });
            for (int i = 1; i <= n; i++) bitchg(i, a[i], 1);
            for (int i = 1; i <= m; i++)
                if (q[i].t == 'C') q[i].val = hafn(q[i].val);
            for (int j = 1; j <= m; j++) {
                auto i = q[j];
                if (i.t == 'C') {
                    bitchg(i.p, a[i.p], -1);
                    a[i.p] = i.val;
                    bitchg(i.p, a[i.p], 1);
                } else {
                    int id = bitask(i.l, i.r, i.val);
                    printf("%d\n", x[id - 1]);
                }
            }
        //}
        return 0;
    }
    

    树状数组套线段数哦

  • 0
    @ 2017-03-04 17:52:10
    #include<algorithm>
    #include<iostream>
    #include<iomanip>
    #include<cstring>
    #include<cstdlib>
    #include<vector>
    #include<cstdio>
    #include<cmath>
    #include<queue>
    using namespace std;
    inline const int Get_Int() {
        int num=0,bj=1;
        char x=getchar();
        while(x<'0'||x>'9') {
            if(x=='-')bj=-1;
            x=getchar();
        }
        while(x>='0'&&x<='9') {
            num=num*10+x-'0';
            x=getchar();
        }
        return num*bj;
    }
    //平衡树套线段树 
    const int maxst=200005,maxbbt=1000005;
    struct bTree {
        int father,child[2]; //0左儿子 1右儿子
        int key,size; //key为结点属性 size为子树大小
        bTree() {}
        bTree(int fa,int lc,int rc,int data,int sz):father(fa),key(data),size(sz) {
            child[0]=lc,child[1]=rc;
        }
    };
    struct Splay {
        bTree tree[maxbbt];
        void init() {
            memset(tree,0,sizeof(tree));
        }
        void clear(int index) {
            tree[index]=bTree(0,0,0,0,0);
        }
        int checkson(int index) { //判断是父亲的左儿子还是右儿子
            return tree[tree[index].father].child[1]==index;
        }
        void update(int index) { //更新size
            if(!index)return;
            tree[index].size=1;
            if(tree[index].child[0])tree[index].size+=tree[tree[index].child[0]].size;
            if(tree[index].child[1])tree[index].size+=tree[tree[index].child[1]].size;
        }
        void rotate(int index) { //旋转到根
            int father=tree[index].father,grandpa=tree[father].father,side=checkson(index);
            tree[father].child[side]=tree[index].child[side^1];
            tree[tree[father].child[side]].father=father;
            tree[father].father=index;
            tree[index].child[side^1]=father;
            tree[index].father=grandpa;
            if(grandpa)tree[grandpa].child[tree[grandpa].child[1]==father]=index;
            update(father);
            update(index);
        }
        void splay(int& root,int index) {
            if(index==root)return;
            for(int father; (father=tree[index].father); rotate(index)) //基本旋转
                if(tree[father].father)rotate((checkson(index)==checkson(father))?father:index); //附加旋转
            root=index;
        }
        void insert(int& root,int index,int v) {
            if(!root) {
                root=index;
                tree[index]=bTree(0,0,0,v,1);
                return;
            }
            int now=root,father=0;
            while(true) {
                father=now; //保存父亲
                now=tree[now].child[tree[now].key<v]; //往哪边走
                if(!now) {
                    tree[index]=bTree(father,0,0,v,1);
                    tree[father].child[tree[father].key<v]=index;
                    update(father);
                    splay(root,index);
                    break;
                }
            }
        }
        void remove(int& root) { //删除根 
            if(!tree[root].child[0]||!tree[root].child[1]) { //只有左右儿子 
                int oldroot=root;
                root=tree[root].child[tree[root].child[0]==0];
                tree[root].father=0;
                clear(oldroot);
                return; 
            }
            int pre=inline_pre_next(root,0),oldroot=root;
            splay(root,pre); //伸展前驱 
            tree[tree[oldroot].child[1]].father=root; //将原根右子树接到根上(相当于删除了)
            tree[root].child[1]=tree[oldroot].child[1];
            clear(oldroot);
            update(root); 
        }
        int inline_pre_next(int& root,int bj) {
            int now=tree[root].child[bj];
            while(tree[now].child[bj^1])now=tree[now].child[bj^1];
            return now;
        }
        int find(int& root,int rank) { //在root为根的树中找到排名为rank的点,返回下标
            int now=root;
            while(true) {
                if(rank<=0||now<=0)return -1; //找不到 
                if(tree[now].child[0]&&rank<=tree[tree[now].child[0]].size)now=tree[now].child[0];
                else {
                    int tmp=(tree[now].child[0]?tree[tree[now].child[0]].size:0)+1;
                    if(rank<=tmp)return now;
                    rank-=tmp;
                    now=tree[now].child[1];
                }
            }
        }
    } bbt;
    int n;
    struct sTree {
        int left,right,root; //记录对应平衡树编号 
        sTree() {}
        sTree(int l,int r,int roo):left(l),right(r),root(roo) {}
    };
    struct Segment_Tree {
        sTree tree[maxst];
        void init() {
            memset(tree,0,sizeof(tree));
            bbt.init();
        }
        void build(int index,int depth,int Left,int Right,int* a) {
            tree[index]=sTree(Left,Right,0);
            if(Left==Right) { //叶子节点 
                bbt.insert(tree[index].root,(depth-1)*n+Left,a[Left]); //对应编号(类似分层图)
                return; 
            }
            int mid=(Left+Right)>>1;
            build(index<<1,depth+1,Left,mid,a);
            build((index<<1)|1,depth+1,mid+1,Right,a);
            for(int i=Left; i<=Right; i++)bbt.insert(tree[index].root,(depth-1)*n+i,a[i]); //路径上的都要建 
        }
        void modify(int index,int depth,int pos,int v) {
            int M=(depth-1)*n+pos; //计算出平衡树中编号
            bbt.splay(tree[index].root,M);
            bbt.remove(tree[index].root);
            bbt.insert(tree[index].root,M,v);
            int l=tree[index].left,r=tree[index].right;
            if(l==r)return;
            int mid=(l+r)>>1;
            if(pos<=mid)modify(index<<1,depth+1,pos,v);
            else modify((index<<1)|1,depth+1,pos,v);
        }
        int query(int index,int Left,int Right,int v) { //统计比v小的个数 
            if(tree[index].right<Left||tree[index].left>Right)return 0;
            if(Left<=tree[index].left&&Right>=tree[index].right) { //完全包含 
                int Now=tree[index].root,sum=0;
                while(Now) {
                    if(bbt.tree[Now].key<v)sum+=bbt.tree[bbt.tree[Now].child[0]].size+1;
                    Now=bbt.tree[Now].child[bbt.tree[Now].key<v];
                }
                return sum;
            }
            return query(index<<1,Left,Right,v)+query((index<<1)|1,Left,Right,v);
        }
        int find(int Left,int Right,int rank) { //寻找第rank小的数 
            int Now=tree[1].root,ans=0;
            if(Left==1&&Right==n)return bbt.tree[bbt.find(Now,rank)].key; //特殊情况
            while(Now) { //二分查找 
                if(query(1,Left,Right,bbt.tree[Now].key)<=rank-1) {
                    ans=bbt.tree[Now].key;
                    Now=bbt.tree[Now].child[1];
                } else Now=bbt.tree[Now].child[0];
            }
            return ans;
        }
    } st;
    int m,a[50005];
    int main() {
        n=Get_Int();
        m=Get_Int();
        st.init();
        for(int i=1; i<=n; i++)a[i]=Get_Int();
        st.build(1,1,1,n,a);
        for(int i=1; i<=m; i++) {
            char order='a';
            while(order!='C'&&order!='Q')order=getchar();
            int x=Get_Int(),y=Get_Int();
            if(order=='Q') {
                int val=Get_Int();
                printf("%d\n",st.find(x,y,val));
            } else st.modify(1,1,x,y);
        }
        return 0;
    }
    
  • 0
    @ 2016-04-19 19:45:31

    以此纪念我的第一个树套树:

    测试数据 #0: Accepted, time = 250 ms, mem = 21704 KiB, score = 10
    测试数据 #1: Accepted, time = 359 ms, mem = 21708 KiB, score = 10
    测试数据 #2: Accepted, time = 78 ms, mem = 21708 KiB, score = 10
    测试数据 #3: Accepted, time = 296 ms, mem = 21712 KiB, score = 10
    测试数据 #4: Accepted, time = 234 ms, mem = 21704 KiB, score = 10
    测试数据 #5: Accepted, time = 406 ms, mem = 21708 KiB, score = 10
    测试数据 #6: Accepted, time = 437 ms, mem = 21716 KiB, score = 10
    测试数据 #7: Accepted, time = 343 ms, mem = 21708 KiB, score = 10
    测试数据 #8: Accepted, time = 453 ms, mem = 21704 KiB, score = 10
    测试数据 #9: Accepted, time = 140 ms, mem = 21708 KiB, score = 10
    Accepted, time = 2996 ms, mem = 21716 KiB, score = 100

    #include<stdio.h>
    #include<algorithm>
    #include<iostream>
    using namespace std;
    //data默认为int类型,如果要进行修改,请定义新的类型,并重载比较运算符
    struct DATA{
        int x;
        DATA (int t){
            x=t;
        }
        DATA (){}
    };
    bool operator < (const DATA a,const DATA b){
        return a.x<b.x;
    }
    bool operator > (const DATA a,const DATA b){
        return a.x>b.x;
    }
    bool operator == (const DATA a,const DATA b){
        return a.x==b.x;
    }
    bool operator != (const DATA a,const DATA b){
        return a.x!=b.x;
    }
    struct data_class{
        int HASH;
        DATA data;
        data_class(int h,DATA d){
            HASH=h;data=d;
        }
        data_class(){}
    };
    bool operator < (const data_class a,const data_class b){
        return (a.data<b.data||a.data==b.data&&a.HASH<b.HASH);
    }
    bool operator > (const data_class a,const data_class b){
        return (a.data>b.data||a.data==b.data&&a.HASH>b.HASH);
    }
    bool operator == (const data_class a,const data_class b){
        return a.data==b.data&&a.HASH==b.HASH;
    }
    bool operator >= (const data_class a,const data_class b){
        return a>b||a==b;
    }
    struct sbt
    {
        int left,right,size;
        data_class data;
        sbt(){
            left=right=0;
            size=0;
        }
    };
    sbt tree[1000000];
    int top;
    struct SBT{
    public:
        int root;
        SBT(){
            root=0;
        }
        int datacmp(const data_class a,const data_class b){
            if (a.data<b.data) return 1;
            if (a.data>b.data) return -1;
            return 0;
        }
        //如果要维护父亲节点和儿子节点的其他域值则修改adapt
        void adapt(int x){
            tree[x].size=tree[tree[x].left].size+tree[tree[x].right].size+1;
        }
        DATA getDATA(int n){
            return tree[n].data.data;
        }
        void left_rot(int &x){
            int y=tree[x].right;
            tree[x].right=tree[y].left;
            tree[y].left=x;
            tree[y].size=tree[x].size;
            adapt(x);
            x=y;
        }
        void right_rot(int &x){
            int y=tree[x].left;
            tree[x].left=tree[y].right;
            tree[y].right=x;
            tree[y].size=tree[x].size;
            adapt(x);
            x=y;
        }
        void Maintain(int &x,bool flag){
            if (!flag){
                if (tree[tree[tree[x].left].left].size>tree[tree[x].right].size)
                    right_rot(x);
                else
                if (tree[tree[tree[x].left].right].size>tree[tree[x].right].size)
                    left_rot(tree[x].left),right_rot(x);
                else
                return;
            }
            else{
                if (tree[tree[tree[x].right].right].size>tree[tree[x].left].size)
                    left_rot(x);
                else
                if (tree[tree[tree[x].right].left].size>tree[tree[x].left].size)
                    right_rot(tree[x].right),left_rot(x);
                else
                return;
            }
            Maintain(tree[x].left,0);
            Maintain(tree[x].right,1);
            Maintain(x,1);
            Maintain(x,0);
        }
        void insert(int &x,data_class data){
            if (x==0){
                x=++top;
                tree[x].size=1;
                tree[x].left=tree[x].right=0;
                tree[x].data=data;
            }
            else{
                tree[x].size++;
                if (data<tree[x].data) insert(tree[x].left,data);
                else insert(tree[x].right,data);
                Maintain(x,data>=tree[x].data);
            }
        }
        int remove(int fa,int &x,data_class data){
            if (!x) return 0;
            tree[x].size--;
            if (datacmp(data,tree[x].data)==-1)
                remove(x,tree[x].right,data);
            else
            if (datacmp(data,tree[x].data)==1)
                remove(x,tree[x].left,data);
            else{
                if (tree[x].left!=0&&tree[x].right==0){
                    tree[x]=tree[tree[x].left];
                    return x;
                }
                else
                if (tree[x].right!=0&&tree[x].left==0){
                    tree[x]=tree[tree[x].right];
                    return x;
                }
                else
                if (tree[x].left==0&&tree[x].right==0){
                    if (root==x) root=0;
                    if (fa)
                        if (tree[fa].left==x) tree[fa].left=0;
                        else tree[fa].right=0;
                }
                else{
                    int ret=tree[x].right;
                    while (tree[ret].left)
                        ret=tree[ret].left;
                    tree[x].data=tree[ret].data;
                    remove(x,tree[x].right,tree[ret].data);
                }
            }
        }
        data_class select(int &x,int k){
            int r=tree[tree[x].left].size+1;
            if (k<r) return select(tree[x].left,k);
            else
            if (k>r) return select(tree[x].right,k-r);
            else
            return tree[x].data;
        }
        int rank(int &x,data_class data){
            if (x==0) return 0;
            if (data>tree[x].data) return tree[tree[x].left].size+1+rank(tree[x].right,data);
            else
            if (data<tree[x].data) return rank(tree[x].left,data);
            else
            return tree[tree[x].left].size+1;
        }
        //插入一个数
        void Insert(int data){
            insert(root,data_class(top+1,data));
        }
        //删除一个数,在相同的情况下,任意删除其中一个
        void Remove(int data){
            remove(0,root,data_class(0,data));
        }
        //查询第k小的数字
        DATA Select(int k){
            return select(root,k).data;
        }
        //查询比data小(严格)的数字有多少个
        int Rank(int data){
            return rank(root,data_class(-1,data));
        }
        //查找data是否存在
        bool Find(int data){
            if (!root) return 0;
            else {
                int x=root;
                while (tree[x].data.data!=data&&x){
                    if (tree[x].data.data<data) x=tree[x].right;
                    else x=tree[x].left;
                }
                if (!x) return 0;
                else if (tree[x].data.data==data) return 1;
            }
        }
        //统计data一共有多少个
        int Count(int data){
            bool exi=Find(data);
            if (exi){
                int aaa=Rank(data);
                int bbb=Rank(data+1);
                return bbb-aaa;
            }
            else return 0;
        }
    };
    struct INTERVAL_DATA{
        int left,right;
        SBT SET;
        INTERVAL_DATA(){
            left=right=0;
        }
    };
    int st[10000],TOP=-1;
    struct INTERVAL_TREE{
        int n;
        INTERVAL_DATA *tree;
        INTERVAL_TREE(int height){
            tree=new INTERVAL_DATA[2<<height];
            n=height;
    
            int h=0;
            tree[0].left=0;tree[0].right=(1<<n)-1;
            for (int i=0;i<((1<<n)-1);i++){
                if (i>(2<<h)-2) h++;
                tree[i*2+1].left=tree[i].left;
                tree[i*2+2].left=(1<<(n-h-1))|tree[i].left;
                tree[i*2+1].right=tree[i*2+1].left+(1<<(n-h-1))-1;
                tree[i*2+2].right=tree[i*2+2].left+(1<<(n-h-1))-1;
            }
            tree[0].left++;tree[0].right++;
            for (int i=0;i<(1<<n)-1;i++){
                tree[i*2+1].left++;tree[i*2+1].right++;
                tree[i*2+2].left++;tree[i*2+2].right++;
            }
        }
        void add(int index,int x){
            index+=(1<<n)-2;
            while (index){
                tree[index].SET.Insert(x);
                index=(index-1)>>1;
            }
            tree[0].SET.Insert(x);
        }
        void change(int index,int y){
            index+=(1<<n)-2;
            int x=tree[index].SET.getDATA(tree[index].SET.root).x;
            while (index){
                tree[index].SET.Remove(x);
                tree[index].SET.Insert(y);
                index=(index-1)>>1;
            }
            tree[0].SET.Remove(x);
            tree[0].SET.Insert(y);
        }
        void getinterval(int root,int l,int r){
            if (tree[root].left==l&&tree[root].right==r) st[++TOP]=root;
            else {
                int mid=(tree[root].left+tree[root].right)/2;
                if (r<=mid) getinterval(root*2+1,l,r);
                else if (l>mid) getinterval(root*2+2,l,r);
                else {
                    getinterval(root*2+1,l,mid);
                    getinterval(root*2+2,mid+1,r);
                }
            }
        }
    } a(16);
    void shownode(int x){
        cout<<tree[x].data.data.x<<' ';
        if (tree[x].left) shownode(tree[x].left);
        if (tree[x].right) shownode(tree[x].right);
    }
    void show(SBT x){
        shownode(x.root);
        cout<<endl;
    }
    int getans(int I,int J,int K){
        TOP=-1;
        K--;
        a.getinterval(0,I,J);
    
        int Max=1000000000,Min=-1,tmp=0,RANK;
        while (Max-Min>1){
            tmp=(Max+Min)/2;
            RANK=0;
            for (int i=0;i<=TOP;i++)
                RANK+=a.tree[st[i]].SET.Rank(tmp);
            if (RANK<=K) Min=tmp;
            else Max=tmp;
        }
        return Min;
    }
    int main(){
        int n,m,tmp;
        scanf("%d%d",&n,&m);
        for (int i=1;i<=n;i++){
            scanf("%d",&tmp);
            a.add(i,tmp);
        }
    
        char ord[3];
        int I,J,K;
        for (int i=1;i<=m;i++){
            scanf("%s",ord);
            if (ord[0]=='Q'){
                scanf("%d%d%d",&I,&J,&K);
                cout<<getans(I,J,K)<<endl;
            }
            else {
                scanf("%d%d",&I,&J);
                a.change(I,J);
            }
        }
        return 0;
    }
    
  • 0
    @ 2016-04-09 19:24:17

    貌似不允许在讨论区发题解(防止剧透?) (。_。)

    平方分割:http://www.cnblogs.com/Onlynagesha/p/5355133.html

  • 0
    @ 2015-02-07 15:26:04

    由于懒得离散化....
    树状数组套动态开点的线段树...
    不论卡内存还是卡时间都特别紧.......
    还好水过了......

    PS: 时限是5s?????

    Accepted, time = 281 ms, mem = 160984 KiB, score = 10
    Accepted, time = 453 ms, mem = 160980 KiB, score = 10
    Accepted, time = 78 ms, mem = 160984 KiB, score = 10
    Accepted, time = 281 ms, mem = 160984 KiB, score = 10
    Accepted, time = 234 ms, mem = 160984 KiB, score = 10
    Accepted, time = 468 ms, mem = 160984 KiB, score = 10
    Accepted, time = 468 ms, mem = 160980 KiB, score = 10
    Accepted, time = 343 ms, mem = 160988 KiB, score = 10
    Accepted, time = 468 ms, mem = 160984 KiB, score = 10
    Accepted, time = 125 ms, mem = 160988 KiB, score = 10

    代码百把行....相当于打个树链剖分...

    Code

    const int INF=(1<<30)-1;

    int n;
    struct node*nil;
    struct node
    {
    int v; //total
    node*l,*r;
    void update()
    { v=l->v+r->v; }
    }pool[13000000];
    node*nt=pool;
    node*newnode()
    {
    nt->l=nt->r=nil;
    nt->v=0;
    return nt++;
    }

    int cp,cv;

    //Sub segment trees
    struct SegmentTree
    {
    node*root;

    node*Change(node*x,int l=0,int r=INF)
    {
    if(cp<l || r<cp) return x;
    if(x==nil) x=newnode();
    if(l==r) { x->v+=cv; return x; }
    int mid=avg(l,r);
    x->l=Change(x->l,l,mid);
    x->r=Change(x->r,mid+1,r);
    x->update();
    return x;
    }

    void Set(int p,int v)
    {
    if(root<pool) root=nil;
    cp=p;
    cv=v;
    root=Change(root);
    }
    };

    //original segment tree
    //performed as tree array

    #define bt(x) (x&-x)

    int a[1000000]; //this array must be stay here....
    SegmentTree t[1000000];
    void Change(int p,int s,int v) //location of point, value of point, delete or add in.
    { for(int i=p;i<=n;i+=bt(i)) t[i].Set(s,v); }

    node*c[1000];
    int adt,ct;

    int Query(int l,int r,int k) //find the element which is rank k.
    {
    adt=0;

    for(int i=r;i>0;i-=bt(i))
    c[adt++]=t[i].root;

    ct=adt;
    for(int i=l-1;i>0;i-=bt(i))
    c[ct++]=t[i].root;

    //we perform add when i<adt, and than dec when adt<=i<ct

    l=0,r=INF;
    while(l!=r)
    {
    //for(int i=0;i<ct;i++)
    //cout<<c[i]<<' '; cout<<endl; cout<<l<<' '<<r<<endl; cout<<endl;

    int mid=avg(l,r);
    int clv=0; //current node's left node count.

    for(int i=0;i<adt;i++)
    clv+=c[i]->l->v;
    for(int i=adt;i<ct;i++)
    clv-=c[i]->l->v;

    if(k<=clv) //the element we want find is on the left block
    {
    for(int i=0;i<ct;i++)
    c[i]=c[i]->l;
    r=mid;
    }
    else
    {
    for(int i=0;i<ct;i++)
    c[i]=c[i]->r;
    k-=clv;
    l=mid+1;
    }
    }

    return l;
    }

    int q;

    int main()
    {
    nil=newnode();
    nil->l=nil->r=nil;
    nil->v=0;

    n=getint();
    q=getint();
    for(int i=0;i<n;i++)
    Change(i+1,a[i+1]=getint(),1);

    for(int i=0;i<q;i++)
    {
    char c[5];
    scanf("%s",c);
    if(c[0]=='C')
    {
    int i=getint();
    int v=getint();
    Change(i,a[i],-1);
    Change(i,a[i]=v,1);
    }
    else
    {
    int i=getint();
    int j=getint();
    int k=getint();
    printf("%d\n",Query(i,j,k));
    }
    }

    return 0;
    }

  • 0
    @ 2014-10-09 09:19:54

    主席树随便搞?

  • 0
    @ 2014-03-14 14:20:15

    线段树套treap也可做
    一开始试了一下线段树套Splay,不知道是写萎了还是什么...TLE了很久...

  • 0
    @ 2013-10-16 18:57:13

    树状数组套主席树:
    #include <cstdio>
    #include <algorithm>
    #include <cstring>
    #include <cstdlib>

    using namespace std;

    #define MAXN 50001
    #define lowbit(x)(((~(x))+1)&x)
    #define MAXM 10001
    #define For(i,x) for (int i=x;i;i-=lowbit(i))
    #define Rep(i,x) for (int i=x;i<=n;i+=lowbit(i))
    #define MAXT 20

    void getint(int &t) {
    scanf("%d",&t);
    }

    void putint(int t) {
    printf("%d\n",t);
    }

    struct saver {
    int v,t;
    } num[MAXN+MAXM];
    int R[MAXN+MAXM],C[MAXN+MAXM],RN=0;

    bool cmp(saver x,saver y) {
    return x.v<y.v;
    }

    int a[MAXN];
    int Query[MAXM][4];
    int n,m,V=0;

    struct node {
    int s;
    int left,right;
    node () {
    s=left=right=0;
    }
    } Node[MAXN*MAXT*MAXT];

    int T[MAXN];
    int M=0;

    void build(int l,int r,int &t) {
    if (!t) t=++M;
    if (l==r) return ;
    int mid=(l+r)>>1;
    build(l,mid,Node[t].left),build(mid+1,r,Node[t].right);
    }

    void Add(int x,int y,int l,int r,int u,int t) {
    Node[t].s=Node[u].s+y;
    if (l==r) return ;
    int mid=(l+r)>>1;
    if (x<=mid) {
    Node[t].right=Node[u].right;
    Add(x,y,l,mid,Node[u].left, Node[t].left=++M);
    } else {
    Node[t].left=Node[u].left;
    Add(x,y,mid+1,r,Node[u].right,Node[t].right=++M);
    }
    }

    void INIT() {
    getint(n),getint(m);
    for (int i=0;i++<n;) {
    getint(a[i]);
    num[++V].v=a[i];
    num[V].t=i;
    }
    for (int i=0;i++<m;) {
    int c;
    while (1) {
    c=getchar();
    if (c==int('Q')||c==int('C')) break;
    }
    if (c==int('Q')) {
    Query[i][0]=1;
    getint(Query[i][1]),getint(Query[i][2]),getint(Query[i][3]);
    } else {
    Query[i][1]=0;
    getint(Query[i][1]),getint(Query[i][2]);
    num[++V].v=Query[i][2];
    num[V].t=n+i;
    }
    }
    sort(num+1,num+V+1,cmp);
    C[++RN]=num[1].v,R[num[1].t]=1;
    for (int i=1;i++<V;) {
    if (num[i].v!=num[i-1].v) {
    C[++RN]=num[i].v;
    }
    R[num[i].t]=RN;
    }
    memset(T,0,sizeof(T));
    build(1,RN,T[0]);
    for (int i=0;i++<n;) {
    int p=T[0];
    for (int j=i-lowbit(i);j++<i;) {
    Add(R[j],1,1,RN,p,T[i]=++M);
    p=T[i];
    }
    }
    }

    int t1[MAXT],t2[MAXT];
    int n1,n2,sum;

    void Solve() {
    for (int i=0;i++<m;) {
    if (!Query[i][0]) {
    int p;
    Rep(j,Query[i][1]) {
    Add(R[Query[i][1]],-1,1,RN,T[j],p=++M);
    T[j]=p;
    }
    Rep(j,Query[i][1]) {
    Add(R[n+i],1,1,RN,T[j],p=++M);
    T[j]=p;
    }
    R[Query[i][1]]=R[n+i];
    } else {
    n1=n2=0;
    For(j,Query[i][2]) t1[++n1]=T[j];
    For(j,Query[i][1]-1) t2[++n2]=T[j];
    int l=1,r=RN;
    while (l!=r) {
    sum=0;
    for (int j=0;j++<n1;) sum+=Node[Node[t1[j]].left].s;
    for (int j=0;j++<n2;) sum-=Node[Node[t2[j]].left].s;
    if (sum>=Query[i][3]) {
    r=(l+r)>>1;
    for (int j=0;j++<n1;) t1[j]=Node[t1[j]].left;
    for (int j=0;j++<n2;) t2[j]=Node[t2[j]].left;
    } else {
    Query[i][3]-=sum;
    l=((l+r)>>1)+1;
    for (int j=0;j++<n1;) t1[j]=Node[t1[j]].right;
    for (int j=0;j++<n2;) t2[j]=Node[t2[j]].right;
    }
    }
    putint(C[l]);
    }
    }
    }

    int main() {
    INIT();
    Solve();
    return 0;
    }

  • 0
    @ 2013-09-14 11:12:06

    树状数组套函数式线段树+离散化
    时间复杂度:O((n+m)log(n+m)+(n+m)log^2(n+m))

    编译成功

    测试数据 #0: Accepted, time = 187 ms, mem = 158932 KiB, score = 10
    测试数据 #1: Accepted, time = 312 ms, mem = 158940 KiB, score = 10
    测试数据 #2: Accepted, time = 31 ms, mem = 158932 KiB, score = 10
    测试数据 #3: Accepted, time = 109 ms, mem = 158936 KiB, score = 10
    测试数据 #4: Accepted, time = 93 ms, mem = 158936 KiB, score = 10
    测试数据 #5: Accepted, time = 203 ms, mem = 158936 KiB, score = 10
    测试数据 #6: Accepted, time = 218 ms, mem = 158932 KiB, score = 10
    测试数据 #7: Accepted, time = 140 ms, mem = 158936 KiB, score = 10
    测试数据 #8: Accepted, time = 218 ms, mem = 158936 KiB, score = 10
    测试数据 #9: Accepted, time = 31 ms, mem = 158936 KiB, score = 10
    Accepted, time = 1542 ms, mem = 158940 KiB, score = 100

  • 0
    @ 2013-08-20 22:01:55

    树状数组+SBT+二分查找O(n log^2 n + m log^3 m)弱弱AC......

    编译成功

    foo.cpp: In function 'int main()':
    foo.cpp:220:16: warning: format '%s' expects argument of type 'char*', but argument 2 has type 'char (*)[1]' [-Wformat]
    测试数据 #0: Accepted, time = 562 ms, mem = 11920 KiB, score = 10
    测试数据 #1: Accepted, time = 859 ms, mem = 17052 KiB, score = 10
    测试数据 #2: Accepted, time = 93 ms, mem = 3120 KiB, score = 10
    测试数据 #3: Accepted, time = 531 ms, mem = 9072 KiB, score = 10
    测试数据 #4: Accepted, time = 421 ms, mem = 8436 KiB, score = 10
    测试数据 #5: Accepted, time = 765 ms, mem = 17108 KiB, score = 10
    测试数据 #6: Accepted, time = 812 ms, mem = 18616 KiB, score = 10
    测试数据 #7: Accepted, time = 593 ms, mem = 10728 KiB, score = 10
    测试数据 #8: Accepted, time = 796 ms, mem = 15896 KiB, score = 10
    测试数据 #9: Accepted, time = 156 ms, mem = 3684 KiB, score = 10
    Accepted, time = 5588 ms, mem = 18616 KiB, score = 100
    #include <cstdio>
    #include <cstring>

    using namespace std;

    #define MAXN 50001

    struct node {
    int key,s;
    node *left,*right;
    };

    node* t[MAXN];
    node* R[MAXN];
    node *bank=new(node);

    int a[MAXN];
    int n,m;

    int lowbit(int x){
    return ((~x)+1)&x;
    }

    //--------------Size_Balanced_Tree------------------

    int left_ratote(node* &t){
    node *k=(*t).right;
    (*t).right=(*k).left;
    (t).s=((t).left).s+((*t).right).s+1;
    (*k).left=t;
    (*k).s=(t).s+((*k).right).s+1;
    t=k;
    return 0;
    }

    int right_ratote(node* &t){
    node *k=(*t).left;
    (*t).left=(*k).right;
    (t).s=((t).left).s+((*t).right).s+1;
    (*k).right=t;
    (k).s=((*k).left).s+(*t).s+1;
    t=k;
    return 0;
    }

    int maintain(node* &t){
    if ((((t).left).left).s>((*t).right).s){
    right_ratote(t);
    maintain((t).right);
    maintain(t);
    return 0;
    }
    if ((
    (*(t).left).right).s>((*t).right).s){
    left_ratote((*t).left);
    right_ratote(t);
    maintain((*t).left);
    maintain((t).right);
    maintain(t);
    return 0;
    }
    if ((
    (*(t).right).right).s>((*t).left).s){
    left_ratote(t);
    maintain((t).left);
    maintain(t);
    return 0;
    }
    if ((
    (*(t).right).left).s>((*t).left).s){
    right_ratote((*t).right);
    left_ratote(t);
    maintain((*t).left);
    maintain((*t).right);
    return 0;
    }
    return 0;
    }

    int INSERT(int key,node* &t){
    if (t==bank){
    t=new(node);
    (*t).left=(*t).right=bank;
    (*t).s=1;
    (*t).key=key;
    return 0;
    }
    (*t).s++;
    if (key<=(*t).key){
    INSERT(key,(*t).left);
    } else INSERT(key,(*t).right);
    maintain(t);
    return 0;
    }

    int DELETE(int key,node* &t){
    if (key==(*t).key){
    if ((*t).left==bank&&(*t).right==bank){
    delete(t);
    t=bank;
    return 0;
    }
    if ((*t).left==bank){
    node *p=(*t).right;
    delete(t);
    t=p;
    return 0;
    }
    if ((*t).right==bank){
    node *p=(*t).left;
    delete(t);
    t=p;
    return 0;
    }
    right_ratote(t);
    DELETE(key,(*t).right);
    (t).s=((t).left).s+((*t).right).s+1;
    maintain(t);
    return 0;
    }
    if (key<(*t).key){
    DELETE(key,(*t).left);
    } else DELETE(key,(*t).right);
    (t).s=((t).left).s+((*t).right).s+1;
    return 0;
    }

    int get_rank(int key,node *t){
    int rec=0;
    node *p=t;
    while (p!=bank){
    if ((p).key<key){
    rec+=((
    (*p).left).s+1);
    p=(*p).right;
    } else {
    p=(*p).left;
    }
    }
    return rec;
    }

    //----------------Binary_Search--------------------

    node *range[MAXN];
    int rm;

    int GET_RANK(int key){
    int rec=0;
    for (int i=0;i++<rm;){
    rec+=get_rank(key,range[i]);
    }
    return rec;
    }

    int get_ans(int l,int r,int k){
    rm=0;
    int i=r;
    while (i>=l){
    int s=i-lowbit(i)+1;
    if (s>=l){
    range[++rm]=t[i];
    i=s-1;
    } else {
    range[++rm]=R[i];
    i--;
    }
    }
    int left=-0x7fffffff,right=0x7fffffff;
    for (i=0;i++<rm;){
    node *p=range[i];
    while (p!=bank){
    if ((*p).key<left){
    p=(*p).right;
    continue;
    }
    if ((*p).key>right){
    p=(*p).left;
    continue;
    }
    int s=GET_RANK((*p).key);
    if (s==k-1){
    return (*p).key;
    }
    if (s<k-1){
    left=(*p).key;
    p=(*p).right;
    } else {
    right=(*p).key;
    p=(*p).left;
    }
    }
    }
    return left;
    }

    //----------------------------------------------

    int main(){
    (*bank).s=0;
    (*bank).left=(*bank).right=bank;
    scanf("%d%d",&n,&m);
    for (int i=0;i++<n;){
    scanf("%d",&a[i]);
    t[i]=R[i]=bank;
    for (int j=i-lowbit(i);j++<i;){
    INSERT(a[j],t[i]);
    }
    INSERT(a[i],R[i]);
    }
    while (m--){
    char c[1];
    scanf("%s",&c);
    if (c[0]=='Q'){
    int l,r,k;
    scanf("%d%d%d",&l,&r,&k);
    printf("%d\n",get_ans(l,r,k));
    } else {
    int x,y;
    scanf("%d%d",&x,&y);
    int i=x;
    while (i<=n){
    DELETE(a[x],t[i]);
    INSERT(y,t[i]);
    i+=lowbit(i);
    }
    (*R[x]).key=y;
    a[x]=y;
    }
    }
    return 0;
    }

  • 0
    @ 2013-08-06 22:34:25

    这时限。。。这数据。。。直接暴力过。。冷掉~
    测试数据 #0: Accepted, time = 3062 ms, mem = 824 KiB, score = 10
    测试数据 #1: Accepted, time = 6062 ms, mem = 828 KiB, score = 10
    测试数据 #2: Accepted, time = 250 ms, mem = 820 KiB, score = 10
    测试数据 #3: Accepted, time = 3109 ms, mem = 828 KiB, score = 10
    测试数据 #4: Accepted, time = 1937 ms, mem = 832 KiB, score = 10
    测试数据 #5: Accepted, time = 5781 ms, mem = 828 KiB, score = 10
    测试数据 #6: Accepted, time = 5796 ms, mem = 832 KiB, score = 10
    测试数据 #7: Accepted, time = 5015 ms, mem = 820 KiB, score = 10
    测试数据 #8: Accepted, time = 7296 ms, mem = 832 KiB, score = 10
    测试数据 #9: Accepted, time = 812 ms, mem = 824 KiB, score = 10
    Accepted, time = 39120 ms, mem = 832 KiB, score = 100
    代码就免了。。。。直接STL排序

  • 0
    @ 2013-08-06 22:34:15

    这时限。。。这数据。。。直接暴力过。。冷掉~
    测试数据 #0: Accepted, time = 3062 ms, mem = 824 KiB, score = 10
    测试数据 #1: Accepted, time = 6062 ms, mem = 828 KiB, score = 10
    测试数据 #2: Accepted, time = 250 ms, mem = 820 KiB, score = 10
    测试数据 #3: Accepted, time = 3109 ms, mem = 828 KiB, score = 10
    测试数据 #4: Accepted, time = 1937 ms, mem = 832 KiB, score = 10
    测试数据 #5: Accepted, time = 5781 ms, mem = 828 KiB, score = 10
    测试数据 #6: Accepted, time = 5796 ms, mem = 832 KiB, score = 10
    测试数据 #7: Accepted, time = 5015 ms, mem = 820 KiB, score = 10
    测试数据 #8: Accepted, time = 7296 ms, mem = 832 KiB, score = 10
    测试数据 #9: Accepted, time = 812 ms, mem = 824 KiB, score = 10
    Accepted, time = 39120 ms, mem = 832 KiB, score = 100
    代码就免了。。。。直接STL排序

  • 0
    @ 2012-11-04 14:24:47

    ├ 测试数据 01:答案正确... (1681ms, 6460KB)

    ├ 测试数据 02:答案正确... (2664ms, 7436KB)

    ├ 测试数据 03:答案正确... (464ms, 5676KB)

    ├ 测试数据 04:答案正确... (2461ms, 6848KB)

    ├ 测试数据 05:答案正确... (1556ms, 6848KB)

    ├ 测试数据 06:答案正确... (2742ms, 7436KB)

    ├ 测试数据 07:答案正确... (2570ms, 7628KB)

    ├ 测试数据 08:答案正确... (3334ms, 7044KB)

    ├ 测试数据 09:答案正确... (3678ms, 7436KB)

    ├ 测试数据 10:答案正确... (1447ms, 6652KB)

    表示快排改一下也可以做……(好像也慢不了多少啊)

    附上代码:

    type arr=array[0..50001] of longint;

    var a:arr;

    l,r,n,m,i,j,k,pos,w:longint;

    x:char;

    function sort(t,w:longint; a:arr):longint;

    var i,j,mid,o:longint;

    begin

    i:=t; j:=w; mid:=a[(i+j) shr 1];

    repeat

    while a[i]mid do dec(j);

    if ij;

    if k=i-(l-1) then exit(sort(i,w,a)) else

    exit(mid);

    end;

    begin

    readln(n,m);

    for i:=1 to n do read(a[i]); readln;

    for i:=1 to m do

    begin

    read(x);

    if x='Q' then

    begin

    readln(l,r,k);

    writeln(sort(l,r,a));

    end;

    if x='C' then

    begin

    readln(pos,w);

    a[pos]:=w;

    end;

    end;

    end.

  • 0
    @ 2010-07-09 18:16:39

    编译通过...

    ├ 测试数据 01:答案正确... 618ms

    ├ 测试数据 02:答案正确... 976ms

    ├ 测试数据 03:答案正确... 25ms

    ├ 测试数据 04:答案正确... 664ms

    ├ 测试数据 05:答案正确... 415ms

    ├ 测试数据 06:答案正确... 867ms

    ├ 测试数据 07:答案正确... 883ms

    ├ 测试数据 08:答案正确... 898ms

    ├ 测试数据 09:答案正确... 1054ms

    ├ 测试数据 10:答案正确... 290ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分:100 有效耗时:6690ms

    2010-7-9 评测机:6K

    线段树套SBT M*lg^2N*lg(10^9) 140行

    速度被lx神牛BS了...

  • 0
    @ 2010-07-03 13:52:33

    编译通过...

    ├ 测试数据 01:答案正确... 2556ms

    ├ 测试数据 02:答案正确... 4244ms

    ├ 测试数据 03:答案正确... 666ms

    ├ 测试数据 04:答案正确... 3572ms

    ├ 测试数据 05:答案正确... 2291ms

    ├ 测试数据 06:运行超时|格式错误...

    ├ 测试数据 07:答案正确... 4025ms

    ├ 测试数据 08:答案正确... 4916ms

    ├ 测试数据 09:答案正确... 5275ms

    ├ 测试数据 10:运行超时|格式错误...

    ---|---|---|---|---|---|---|---|-

    Unaccepted 有效得分:80 有效耗时:27545ms

    我疯了 vijos mini 这么卡。。。。r~!

  • 0
    @ 2010-04-10 11:08:04

    delete:=key[t];

    if (left[t]=0)or(right[t]=0) then t:=left[t]+right[t]

    else key[t]:=delete(left[t],v);

    忘了写key[t]:=调了很多数据都没发现,

    还有就是排序写好后忘了把sort(1,rr)写上去(就是没掉用)

    我用的是树套树,写到一半才想到树状数组+SBT

    听SWJ神牛说还可以用离散化+二分(这个问题的解是谁)+二维树状数组+hash,

    就是(x,y)表示1-x的区间内1-y的和(离散化后重新编号,暴力赋值(像计数排序))。每次用求x-y的小于k有多少个时,分别求1-x-1,和1-y。

  • 0
    @ 2010-04-04 18:35:55

    树状数组+SBT 200 行

    悲剧的碰上 vag 6K

    编译通过...

    ├ 测试数据 01:答案正确... 306ms

    ├ 测试数据 02:答案正确... 493ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 352ms

    ├ 测试数据 05:答案正确... 181ms

    ├ 测试数据 06:答案正确... 555ms

    ├ 测试数据 07:答案正确... 555ms

    ├ 测试数据 08:答案正确... 602ms

    ├ 测试数据 09:答案正确... 540ms

    ├ 测试数据 10:答案正确... 150ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分:100 有效耗时:3734ms

  • 0
    @ 2009-10-25 20:48:01

    纯线段树不行么?

信息

ID
1665
难度
7
分类
数据结构 | 树套树 点击显示
标签
(无)
递交数
655
已通过
107
通过率
16%
上传者