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;
}

張貼者： 於
標籤：

沒有留言:

張貼留言

訂閱： 張貼留言 (Atom)