latex預處理

\( \newcommand{\ord}[1]{\mathcal{O}\left(#1\right)} \newcommand{\abs}[1]{\lvert #1 \rvert} \newcommand{\floor}[1]{\lfloor #1 \rfloor} \newcommand{\ceil}[1]{\lceil #1 \rceil} \newcommand{\opord}{\operatorname{\mathcal{O}}} \newcommand{\argmax}{\operatorname{arg\,max}} \newcommand{\str}[1]{\texttt{"#1"}} \)

2018年1月16日 星期二

[ TIOJ 1840 ] Coding Days コーディングデイス

題目:
http://tioj.ck.tp.edu.tw/problems/1840
帶修改求區間第k小(可離線)

解法:
本題有多種作法，有些做法複雜度太高接近TLE邊緣所以就不做了，這裡提供兩種做法

解法一，BIT套持久化線段樹:
BIT的每個位置都是一顆持久化線段樹，修改和查詢時就按造BIT的方式進行，因為數字範圍是int範圍，所以要先離散化，缺點就是coding複雜度很高，而且需要的空間不是線性，複雜度為$\ord{(N+Q)logNlog(N+Q)}$，其實可以做到$\ord{N+QlogNlog(N+Q)}$但是懶得做

解法一code:

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
#include<bits/stdc++.h>
#define lowbit(x) (x)&(-x)
#define MAXM 4000010
using namespace std;
struct node{
    int cnt;
    node *l,*r;
    node():cnt(0),l(0),r(0){}
}*root[50005],*bit[50005],*ul[50005],*ur[50005];
node mem[MAXM],*top;
struct Q{
    int l,r,k;
}qu[10005];
int n,q,m,t,in;
int s[50005],h[60005];
node *build(int l,int r){
    node *o=new(top++) node;
    if(l!=r){
        int mid=(l+r)/2;
        o->l=build(l,mid);
        o->r=build(mid+1,r);
    }
    return o;
}
inline node *insert(node *o,int x,int d){
    int l=0,r=m-1,mid;
    node *nt=new(top++) node(*o),*tp=nt;
    nt->cnt+=d;
    while(l<r){
        mid=(l+r)/2;
        if(x<=mid){
            nt->l=new(top++) node(*nt->l);
            nt=nt->l;
            r=mid;
        }else{
            nt->r=new(top++) node(*nt->r);
            nt=nt->r;
            l=mid+1;
        }
        nt->cnt+=d;
    }
    return tp;
}
inline void update(int a,int x,int d){
    for(;a<=n;a+=lowbit(a))bit[a]=insert(bit[a],x,d);
}
inline int cnt(node *o){return o?o->cnt:0;}
inline int sum(int x,node **s){
    int ans=0;
    for(;x;x-=lowbit(x))ans+=cnt(s[x]->l);
    return ans;
}
inline int find(int a,int b,int k){
    node *lt=root[a-1],*rt=root[b];
    int l=0,r=m-1,sa,sb,tp,mid;
    for(int i=a-1;i;i-=lowbit(i))ul[i]=bit[i];
    sa=sum(a-1,ul);
    for(int i=b;i;i-=lowbit(i))ur[i]=bit[i];
    sb=sum(b,ur);
    while(l<r){
        mid=(l+r)/2;
        tp=sb-sa+cnt(rt->l)-cnt(lt->l);
        if(k<=tp){
            r=mid;
            lt=lt->l;
            rt=rt->l;
            for(int i=a-1;i;i-=lowbit(i))ul[i]=ul[i]->l;
            for(int i=b;i;i-=lowbit(i))ur[i]=ur[i]->l;
        }else{
            l=mid+1;
            k-=tp;
            lt=lt->r;
            rt=rt->r;
            for(int i=a-1;i;i-=lowbit(i))ul[i]=ul[i]->r;
            for(int i=b;i;i-=lowbit(i))ur[i]=ur[i]->r;
        }
        sa=sum(a-1,ul);
        sb=sum(b,ur);
    }
    return l;
}
int main(){
    scanf("%d",&t);
    while(t--){
        m=0;
        top=mem;
        scanf("%d%d",&n,&q);
        for(int i=1;i<=n;i++)scanf("%d",&s[i]),h[m++]=s[i];
        for(int i=0;i<q;i++){
            scanf("%d",&in);
            if(in==1)scanf("%d%d%d",&qu[i].l,&qu[i].r,&qu[i].k);
            else if(in==2){
                scanf("%d%d",&qu[i].l,&qu[i].r);
                qu[i].k=-1;
                h[m++]=qu[i].r;
            }else{
                scanf("%d%d",&qu[i].l,&qu[i].r);
                qu[i].k=-2;
            }
        }
        sort(h,h+m);
        m=unique(h,h+m)-h;
        root[0]=build(0,m-1);
        for(int i=1;i<=n;i++){
            bit[i]=root[0];
            root[i]=insert(root[i-1],lower_bound(h,h+m,s[i])-h,1);
        }
        for(int i=0;i<q;i++){
            if(qu[i].k==-2)puts("7122");
            else if(~qu[i].k)printf("%d\n",h[find(qu[i].l,qu[i].r,qu[i].k)]);
            else{
                update(qu[i].l,lower_bound(h,h+m,s[qu[i].l])-h,-1);
                update(qu[i].l,lower_bound(h,h+m,qu[i].r)-h,1);
                s[qu[i].l]=qu[i].r;
            }
        }
    }
    return 0;
}

解法二，整體二分:
整體二分就是把所有操作一起二分搜的意思，這裡的操作包含修改還有查詢。

可以先試著想想只有一次查詢的情況，我們可以對答案(第k小的數)進行二分搜，假設現在搜到二分點mid，我們就掃描整個序列以及所有修改操作，找出有小於等於mid數字的操作，對數列進行這些操作之後把數列中小於等於mid的部分設為1，大於的設為0。然後對於查詢區間$[l,r]$來說，如果序列中$l \sim r$的總和小於所要查詢的k，表示該區間小於等於mid的數都不會是答案，因此要對大於mid的部分進行查找，反之就查小於mid的部分。

可以發現如果每個查詢操作一個一個做二分搜的話，時間複雜度會變成$\ord{QNlogN}$和暴力做一樣糟，因此就誕生了一個大家一起二分搜的做法-----整體二分！
整個算法的框架如下所示

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
void total_binary_search(int l,int r,vector<OPERATOR> VS){
    if(VS.empty()) return;
    if(l==r){
        VS中所有查詢操作的答案就是 r
        return;
    }
    int mid=(l+r)/2;
    vector<OPERATOR> LS,RS;
    將VS中所有修改操作的影響、查詢結果<=mid的部份分到LS，剩下的給RS
    total_binary_search(l,mid,LS);
    total_binary_search(mid+1,r,RS);
}
這只是個初步的想法，實際上二分的這個過程要直接做不是那麼容易，因此大部分常見的情況會是

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
void total_binary_search(int l,int r,vector<OPERATOR> VS){
    if(VS.empty()) return;
    if(l==r){
        VS中所有查詢操作的答案就是 r
        return;
    }
    int mid=(l+r)/2;
    vector<OPERATOR> LS,RS;
    
    do_something();
    divide(VS,LS,RS);
    undo_something();
    
    total_binary_search(l,mid,LS);
    
    do_something();
    total_binary_search(mid+1,r,RS);
    undo_something();
}
通常do_something()和undo_something()會用極短的時間維護一個全域的資料結構，假設操作資料結構的複雜度是$\ord{K}$，則do_something()和undo_something()的複雜度通常會是$\ord{VS.size()} \times \ord{K}$，這樣整體二分複雜度就會是$\ord{(N+Q)K log(N+Q)}$

對這題來說，只要好好維護一個BIT就能做到以上的事情，但是很抱歉，這只有在沒有修改的情況下才會是正確的(請各位想一想為甚麼)，因此要想辦法把上面的第16和第18行拿掉，具體可以看我的實作。

整體二分的好處就是好寫，code短，而且只需要用到線性的記憶體就行了，但是要注意類似本題這樣需要稍微改變模板的情況

code: 

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 50005;
const int MAXM = 10005;
struct OPERATOR{
    // l == -1: 題目中某個特殊條件
    // l == -2: 在r的位置加入k帶來的影響
    // l == -3: 在r的位置移除k帶來的影響
    // else: 查詢[l,r]的第k小元素
    int l,r,k,ans;
}op[MAXN+MAXM*2];
int t,n,q,m;
int s[MAXN];
int bit[MAXN];
inline void add(int x,int d){
    for(;x<=n;x+=(x&-x)) bit[x]+=d;
}
inline int sum(int x){
    int res=0;
    for(;x;x-=(x&-x)) res+=bit[x];
    return res;
}
inline void update_op(int mid,vector<int> &VS,int type,bool modifyAns){
    for(auto i:VS){
        if(op[i].l==-2){
            if(op[i].k<=mid)add(op[i].r,type);
        }else if(op[i].l==-3){
            if(op[i].k<=mid)add(op[i].r,-type);
        }else if(modifyAns){
            op[i].ans=sum(op[i].r)-sum(op[i].l-1);
        }
    }
}
inline void divid(int mid,vector<int> &VS,vector<int> &LV,vector<int> &RV){
    for(auto i:VS){
        if(op[i].l<0){
            if(op[i].k<=mid) LV.emplace_back(i);
            else RV.emplace_back(i);
        }else{
            if(op[i].ans>=op[i].k) LV.emplace_back(i);
            else RV.emplace_back(i),op[i].k-=op[i].ans;//這是關鍵
        }
    }
    vector<int>().swap(VS);
}
void total_binary_search(int l,int r,vector<int> &VS){
    if(VS.empty()) return;
    if(l==r){
        for(auto i:VS) op[i].ans=l;
        return;
    }
    int mid=(l+r)/2;
    
    update_op(mid,VS,1,true);
    vector<int> LV,RV;
    divid(mid,VS,LV,RV);
    update_op(mid,LV,-1,false);
    
    total_binary_search(l,mid,LV);
    
    //update_op(mid,LV,1,false); 不可以把註解拿掉
    total_binary_search(mid+1,r,RV);
    //update_op(mid,LV,-1,false);
}
int main(){
    scanf("%d",&t);
    while(t--){
        scanf("%d%d",&n,&q);
        m=0;
        vector<int> p;
        for(int i=1;i<=n;++i){
            scanf("%d",s+i);
            op[m++]={-2,i,s[i],0};
            p.emplace_back(s[i]);
        }
        int type,l,r,k;
        while(q--){
            scanf("%d",&type);
            if(type==1){
                scanf("%d%d%d",&l,&r,&k);
                op[m++]={l,r,k,0};
            }else if(type==2){
                scanf("%d%d",&r,&k);
                op[m++]={-3,r,s[r],0};
                op[m++]={-2,r,k,0};
                p.emplace_back(s[r]=k);
            }else{
                scanf("%d%d",&r,&k);
                op[m++]={-1,r,k,7122};
            }
        }
        sort(p.begin(),p.end());
        p.erase(unique(p.begin(),p.end()),p.end());
        vector<int> VS;
        for(int i=0;i<m;++i){
            if(op[i].l==-1) continue;
            VS.emplace_back(i);
            if(op[i].l>0) continue;
            op[i].k=lower_bound(p.begin(),p.end(),op[i].k)-p.begin();
        }
        memset(bit+1,0,sizeof(int)*n);
        total_binary_search(0,int(p.size())-1,VS);
        for(int i=n;i<m;++i){
            if(op[i].l==-1)puts("7122");
            else if(op[i].l>0)printf("%d\n",p[op[i].ans]);
        }
    }
    return 0;
}

張貼者： 於 沒有留言:
標籤：

2017年4月27日 星期四

[ uvaLive 5031 ] Graph and Queries

題目:
https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=33&problem=3032

解法:
這題很明顯是名次樹的題目。把所有操作存起來，然後再到著做回來，就可以把刪邊變成增邊。用並查集維護那些點連通，用Treap紀錄那些點的權重，當增加邊的操作造成兩個集合要合併時，使用啟發式合併，總複雜度大約為$\ord{n log n log n}$

我的code中沒有用到任何旋轉的操作，全部都用split和merge完成，證明了只需要會split和merge一樣是可以拿來寫名次樹的

code:
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;
#define MAXN 100005
#define MAXM 1000005
struct node{
    node *l,*r;
    int key;
    unsigned s;
    node(int k):l(0),r(0),key(k),s(1){}
    void up(){
        s=1;
        if(l)s+=l->s;
        if(r)s+=r->s;
    }
};
inline unsigned ran(){
    static unsigned x=time(0);
    return x=x*0xdefaced+1;
}
inline unsigned size(node *o){
    return o?o->s:0;
}
node *merge(node *a,node *b){
    if(!a||!b)return a?a:b;
    if(ran()%(a->s+b->s)<a->s){
        a->r=merge(a->r,b);
        a->up();
        return a;
    }else{
        b->l=merge(a,b->l);
        b->up();
        return b;
    }
}
void split(node *o,node *&a,node *&b,int k){
    if(!o)a=b=0;
    else{
        if(o->key<k){
            a=o;
            split(o->r,a->r,b,k);
        }else{
            b=o;
            split(o->l,a,b->l,k);
        }
        o->up();
    }
}
void insert(node *&o,int k){
    node *a,*b;
    split(o,a,b,k);
    o=merge(a,merge(new node(k),b));
}
void split2(node *o,node *&a,node *&b,unsigned k){
    if(!o)a=b=0;
    else{
        if(k<=size(o->l)){
            b=o;
            split2(o->l,a,b->l,k);
        }else{
            a=o;
            split2(o->r,a->r,b,k-size(o->l)-1);
        }
        o->up();
    }
}
bool erase(node *&o,int k){
    node *a,*b,*c;
    split(o,a,b,k);
    if(!b)return 0;
    split2(b,b,c,1);
    if(b->key==k){
        delete b;
        return o=merge(a,c),1;
    }
    return o=merge(a,merge(b,c)),0;
}
inline int kth(node *&o,int k){
    if((int)size(o)<k||k<1)return 0;
    //注意這裡他會給你不合法的測資，被坑很久
    node *a,*b,*c;
    split2(o,a,c,size(o)-k);
    split2(c,b,c,1);
    o=merge(a,merge(b,c));
    return b->key;
}
struct edge{
    int u,v,use;
    edge():use(0){}
}E[MAXM];
struct XDD{
    char c;
    int p,w;
}g;
vector<XDD> P;
int n,m,t;
int st[MAXN];
int s[MAXN];
int find(int x){
    return st[x]==x?x:st[x]=find(st[x]);
}
node *sa[MAXN];
void dfs(node *&o,node *&x){
    if(!o)return;
    insert(x,o->key);
    dfs(o->l,x);
    dfs(o->r,x);
    delete o;
    o=0;
}
node *strong_merge(node *&a,node *&b){
    if(size(a)<size(b))swap(a,b);
    dfs(b,a);
    return a;
}
int main(){
    int _=0;
    while(scanf("%d%d",&n,&m),n||m){
        for(int i=1;i<=n;++i){
            scanf("%d",&s[i]);
            st[i]=i;
        }
        for(int i=1;i<=m;++i){
            scanf("%d%d",&E[i].u,&E[i].v);
            E[i].use=0;
        }
        P.clear();
        for(char c[10];scanf("%s",c),c[0]!='E';){
            g.c=c[0];
            if(c[0]=='D'){
                scanf("%d",&g.p);
                E[g.p].use=1;
            }else{
                scanf("%d%d",&g.p,&g.w);
                if(c[0]=='C'){
                    swap(s[g.p],g.w);
                }
            }
            P.push_back(g);
        }
        for(int i=1;i<=n;++i){
            sa[i]=new node(s[i]);
        }
        for(int i=1;i<=m;++i){
            int u=find(E[i].u),v=find(E[i].v);
            if(!E[i].use&&u!=v){
                st[u]=v;
                sa[v]=strong_merge(sa[v],sa[u]);
            }
        }
        vector<int> ans;
        for(int i=(int)P.size()-1;i>=0;--i){
            if(P[i].c=='D'){
                int u=find(E[P[i].p].u),v=find(E[P[i].p].v);
                if(u!=v){
                    st[u]=v;
                    sa[v]=strong_merge(sa[v],sa[u]);
                }
            }else if(P[i].c=='Q'){
                ans.push_back(kth(sa[find(P[i].p)],P[i].w));
            }else{
                int p=find(P[i].p);
                erase(sa[p],s[P[i].p]);
                insert(sa[p],P[i].w);
                s[P[i].p]=P[i].w;
            }
        }
        double V=(double)ans.size();
        long long tot=0;
        for(auto i=ans.rbegin();i!=ans.rend();++i)tot+=*i;
        printf("Case %d: %.6lf\n",++_,tot/V);
    }
    return 0;
}

張貼者： 於 沒有留言:
標籤： , ,

2017年3月7日 星期二

[ POJ 1741 ] Tree

題目:
http://poj.org/problem?id=1741

解法:
樹分治，找出重心後，算出通過重心且長度$\leq k$的路徑有幾個，因為我是所有路徑一起算的，所以還要扣掉在同一個子樹的路徑，算路徑會花$\ord{n log n}$，樹分治深度最多$\ord{log n}$，因此總複雜度是$\ord{n log^2 n}$

code:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#include<bits/stdc++.h>
using namespace std;
#define MAXN 10005
int n,k;
vector<pair<int,int> >g[MAXN];
int size[MAXN];
bool vis[MAXN];
inline void init(){
    for(int i=0;i<=n;++i){
        g[i].clear();
        vis[i]=0;
    }
}
void get_dis(vector<int> &dis,int u,int pa,int d){
    dis.push_back(d);
    for(size_t i=0;i<g[u].size();++i){
        int v=g[u][i].first,w=g[u][i].second;
        if(v!=pa&&!vis[v])get_dis(dis,v,u,d+w);
    }
}
vector<int> dis;//這東西如果放在函數裡會TLE
int cal(int u,int d){
    dis.clear();
    get_dis(dis,u,-1,d);
    sort(dis.begin(),dis.end());
    int l=0,r=dis.size()-1,res=0;
    while(l<r){
        while(l<r&&dis[l]+dis[r]>k)--r;
        res+=r-(l++);
    }
    return res;
}
pair<int,int> tree_centroid(int u,int pa,const int sz){
    size[u]=1;//找樹重心，second是重心
    pair<int,int> res(INT_MAX,-1);
    int ma=0;
    for(size_t i=0;i<g[u].size();++i){
        int v=g[u][i].first;
        if(v==pa||vis[v])continue;
        res=min(res,tree_centroid(v,u,sz));
        size[u]+=size[v];
        ma=max(ma,size[v]);
    }
    ma=max(ma,sz-size[u]);
    return min(res,make_pair(ma,u));
}
int tree_DC(int u,int sz){
    int center=tree_centroid(u,-1,sz).second;
    int ans=cal(center,0);
    vis[center]=1;
    for(size_t i=0;i<g[center].size();++i){
        int v=g[center][i].first,w=g[center][i].second;
        if(vis[v])continue;
        ans-=cal(v,w);
        if(size[v]>size[center])
            size[v]=sz-size[center];
        ans+=tree_DC(v,size[v]);
    }
    return ans;
}
int main(){
    while(scanf("%d%d",&n,&k),n||k){
        init();
        for(int i=1;i<n;++i){
            int u,v,w;
            scanf("%d%d%d",&u,&v,&w);
            g[u].push_back(make_pair(v,w));
            g[v].push_back(make_pair(u,w));
        }
        printf("%d\n",tree_DC(1,n));
    }
    return 0;
}

張貼者： 於 沒有留言:
標籤： , ,
訂閱： 文章 (Atom)