蓝书 嵌套+分块

自用笔记算法

蓝书 嵌套+分块

嵌套就是所谓的树套树 第一题为线段树套线段树

uva 11297

题目要求

给出一个n×n的矩阵，有两个操作：查询某个子矩阵的最大值和最小值，将矩阵中的一个数修改为v。

参考AC代码

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
#include<bits/stdc++.h>
#define maxn 550
#define lson rt<<1,l,mid
#define rson rt<<1|1,mid+1,r
#define inf 0x3f3f3f3f
#define mm(a,b) memset(a,b,sizeof(a))
using namespace std;
int n,m,q;
int a[maxn][maxn];
int Max[maxn<<2][maxn<<2],Min[maxn<<2][maxn<<2];
int ansmx,ansmi;
int x1,y11,x2,y2,val;
void push_up1(int rt1,int rt2){
	Max[rt1][rt2]=max(Max[rt1<<1][rt2],Max[rt1<<1|1][rt2]);
	Min[rt1][rt2]=min(Min[rt1<<1][rt2],Min[rt1<<1|1][rt2]); 
}
void push_up2(int rt1,int rt2){
	Max[rt1][rt2]=max(Max[rt1][rt2<<1],Max[rt1][rt2<<1|1]);
	Min[rt1][rt2]=min(Min[rt1][rt2<<1],Min[rt1][rt2<<1|1]);
}
void buildy(int rt,int l,int r,int xrt,int x){
	if(l==r){
		if(x>0) Max[xrt][rt]=Min[xrt][rt]=a[x][l];
		else push_up1(xrt,rt);
		return;
	}
	int mid=l+r>>1;
	buildy(lson,xrt,x);
	buildy(rson,xrt,x);
	push_up2(xrt,rt);
}
void buildx(int rt,int l,int r){
	if(l==r){
		buildy(1,1,m,rt,l);
		return;
	}
	int mid=l+r>>1;
	buildx(lson);
	buildx(rson);
	buildy(1,1,m,rt,-1);
} 
void updatey(int rt,int l,int r,int xrt,int x){
	if(l==r){
		if(x>0) Max[xrt][rt]=Min[xrt][rt]=val;
		else push_up1(xrt,rt);
		return;
	}
	int mid=l+r>>1;
	if(mid>=y11) updatey(lson,xrt,x);
	else updatey(rson,xrt,x);
	push_up2(xrt,rt);
}
void updatex(int rt,int l,int r){
	if(l==r){
		updatey(1,1,m,rt,l);
		return;
	}
	int mid=l+r>>1;
	if(mid>=x1) updatex(lson);
	else updatex(rson);
	updatey(1,1,m,rt,-1);
}
void queryy(int rt,int l,int r,int xrt){
	if(l>=y11 && r<=y2){
		ansmx=max(ansmx,Max[xrt][rt]);
		ansmi=min(ansmi,Min[xrt][rt]);
		return;
	}
	int mid=l+r>>1;
	if(mid>=y11) queryy(lson,xrt);
	if(mid<y2) queryy(rson,xrt);
}
void queryx(int rt,int l,int r){
	if(l>=x1 && r<=x2){
		queryy(1,1,m,rt);
		return;
	}
	int mid=l+r>>1;
	if(mid>=x1) queryx(lson);
	if(mid<x2) queryx(rson);
}
char op[10];
int main(){
//	freopen("input.txt","r",stdin);
	scanf("%d",&n);
	m=n;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++) scanf("%d",&a[i][j]);
	}
	mm(Max,-inf),mm(Min,inf);
	buildx(1,1,n);
	scanf("%d",&q);
	while(q--){
		scanf("%s",op);
		if(op[0]=='q'){
			ansmx=-inf,ansmi=inf;
			scanf("%d%d%d%d",&x1,&y11,&x2,&y2);
			queryx(1,1,n);
			printf("%d %d\n",ansmx,ansmi);
		}
		else{
			scanf("%d%d%d",&x1,&y11,&val);
			updatex(1,1,n);
		}
	}
	return 0;
}

思路

二维线段树裸题
按照x建一颗线段树 每个结点再按照y建一颗线段树

uva 11990

题目要求

给定一个1~n的排列求删除某个数后剩下的逆序对的个数(实际是删除之前的逆序对个数)

参考AC代码(树状数组+BST)

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
#include<bits/stdc++.h>
using namespace std;  
const int N = 200005;  
const int M = N * 20;  
typedef long long LL;  
int arr[N], pos[N], tmp[N];  
LL res;  
inline int lowbit(int t){  
    return t&(-t);  
}  
struct BST{  
    int L[M],R[M],sz[M],V[M],T[N];  
    bool is[M];  
    int n,root[N];  
    int id;  
	LL key;  
    void init(int n){  
        id=1;  
        this->n=n;  
        int l,r;  
        for(int i=1;i<=n;i++){  
            l=i-lowbit(i)+1,r=i;  
            pos[arr[i]]=i;       
            for(int j=l;j<=r;j++) T[j]=arr[j];  
            sort(T+l,T+r+1);  
            build(root[i],l,r);  
        }
    }
    inline void push_up(int rt){  
        sz[rt]=sz[L[rt]]+sz[R[rt]]+is[rt];  
    }  
    void build(int& rt,int l,int r){  
        if(l>r) return;  
        rt=id++;  
        is[rt]=1;  
        int mid=l + r>>1;  
        int v=T[mid];  
        V[rt]=v;  
        L[rt]=R[rt]=0;  
        build(L[rt],l,mid-1);  
        build(R[rt],mid+1,r);  
        push_up(rt);  
    }  
    void remove(int rt,int v){  
        if(rt==0) return;  
        if(v==V[rt]){  
            is[rt]=0;  
            sz[rt]--;  
        }
        else if(v<V[rt]){  
            remove(L[rt],v);  
            push_up(rt);  
        }
        else{  
            remove(R[rt],v);  
            push_up(rt);  
        }   
    }
    int lower(int rt,int v){  
        if(rt==0 || !sz[rt]) return 0;  
        if(v==V[rt]) return sz[L[rt]];    
        else if(v<V[rt]) return lower(L[rt],v);    
        else{
            int tmp=sz[rt]-sz[R[rt]];  
            return tmp+lower(R[rt],v);  
        }         
    }  
    int upper(int rt,int v){  
        if(rt==0) return 0;  
        if (v==V[rt]) return sz[R[rt]];  
        else if(v>V[rt]) return upper(R[rt],v);  
        else{  
            int tmp=sz[rt]-sz[L[rt]];  
            return tmp+upper(L[rt],v);  
        }  
    }  
    void gao(int v){  
        int p=pos[v];  
        int t=p;   
        while(p<=n){  
            remove(root[p],v);  
            p+=lowbit(p);  
        }  
        printf("%lld\n",key);  
        p=t-1;  
        LL cnt=0;  
        while(p){  
            cnt+=upper(root[p],v);  
            cnt-=lower(root[p],v);  
            p-=lowbit(p);  
        }  
        p=n;  
        while(p){  
            cnt+=lower(root[p],v);  
            p-=lowbit(p);  
        }  
        key -= cnt;  
    }  
}T;  
void msort(int* A, int l, int r){  
    if(l<r){  
        int mid=l+r>>1;  
        msort(A,l,mid);  
        msort(A,mid+1,r);  
        int p=l,q=mid+1,id=l;  
        while(p<=mid || q<=r){  
            if(q>r || p<=mid && A[p]<=A[q]) tmp[id++]=A[p++];  
            else{  
                res+=mid-p+1;  
                tmp[id++]=A[q++];  
            }  
        }  
        for(int i=l;i<=r;i++) arr[i]=tmp[i];  
    }  
}
int main(){
//	freopen("input.txt","r",stdin);
    int n, m, v;  
    while(~scanf("%d%d",&n,&m)){  
        for(int i=1;i<=n;i++) scanf("%d",&arr[i]);  
        T.init(n);  
        res=0; 
        msort(arr,1,n);  
        T.key=res;  
        for (int i=0;i<m;i++){  
            scanf("%d",&v);  
            T.gao(v);  
        }         
    }  
    return 0;  
}

参考AC代码(树状数组+cdq分治)

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
#include<bits/stdc++.h>
using namespace std;
const int N=200005;  
typedef long long LL;  
int A[N],pos[N],ans[N],del[N],op[N],t1[N],to[N],key[N];  
LL c[N];  
int n;  
void add(int p){
    while(p<=n){  
        c[p]+=1;  
        p+=p&-p;  
    }
}
void sub(int p){
    while(p<=n){
        c[p]-=1;
        p+=p&-p;
    }
}
int sum(int m){
    int res=0;
    while(m){
        res+=c[m];
        m-=m&-m;
	}
    return res;
}
void solve(int l,int r,bool flag){
    if(l>=r) return;
    int mid=l+r>>1;
    int p=l,q=mid+1;
    for(int i=l;i<=r;i++) t1[op[i]<=mid?p++:q++]=op[i];
    copy(t1+l,t1+r+1,op+l);
    int cur=l;
    for(int i=mid+1;i<=r;i++){
        int x=op[i];
        if(!flag){
            while(cur<=mid && del[op[cur]]<del[x]){
                add(pos[del[op[cur]]]);
                cur++;
            }
            ans[x]-=sum(n)-sum(pos[del[x]]);
        }
        else{
            while(cur<=mid && del[op[cur]]>del[x]){
                add(pos[del[op[cur]]]);
                cur++;
            }
            ans[x]-=sum(pos[del[x]]);
        }
    }
    for(int i=l;i<cur;i++) sub(pos[del[op[i]]]);
    solve(l,mid,flag);
	solve(mid+1,r,flag);
}  
bool cmp(const int& a,const int& b){
    return del[a]<del[b];
}
bool cmp2(const int& a,const int& b){
    return del[a]>del[b];
}
LL res;
void msort(int l,int r){
    if(l>=r) return;
    int mid=l+r>>1;
    int p=l,q=mid+1,id=l;
    msort(l,mid);
    msort(mid+1,r);
    while(p<=mid || q<=r) {  
        if(q>r || (p<=mid && A[p]<A[q])) t1[id++]=A[p++];  
        else{
            res+=mid-p+1;  
            t1[id++]=A[q++];  
        }
    }
    copy(t1+l,t1+r+1,A+l);  
} 
int main(){
//	freopen("input.txt","r",stdin);
    int m; 
    while(~scanf("%d%d",&n,&m)){  
        for(int i=1;i<=n;i++){
        	scanf("%d",A+i);
			pos[A[i]]=i,op[i]=i;  
		}
        for(int i=1;i<=m;i++) scanf("%d",del+i);  
        memset(c,0,sizeof(c));
        for(int i=1;i<=n;i++){
            int tmp=sum(A[i]);
            key[i]=sum(n)-tmp;
            add(A[i]);
            key[i]+=A[i]-1-tmp;
        }  
        memset(c,0,sizeof(c));  
        for(int i=1;i<=m;i++) ans[i]=key[pos[del[i]]];  
        res = 0;
        msort(1,n);
        sort(op+1,op+1+m,cmp);
        solve(1,m,0);
        sort(op+1,op+1+m,cmp2);
        solve(1,m,1);
        for(int i=1;i<=m;i++){
            printf("%lld\n",res);
            res-=ans[i];
        }
    }
    return 0;
}

思路

蓝书p392
树套树结构
后续补上

uva 12003

题目要求

蓝书P393
n个数m次询问
统计区间内严格小于v的个数k 再根据k单点修改
问修改后的数组是什么

参考AC代码

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
#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int maxn = 300050;
int n,m,u,num;
int belong[maxn],block,l[maxn],r[maxn],a[maxn];
int d[maxn];
void build(){
    block=sqrt(n);
    num=n/block;
	if(n%block) num++;
    for(int i=1;i<=num;i++) l[i]=(i-1)*block+1,r[i]=i*block;
    r[num]=n;
    for(int i=1;i<=n;i++) belong[i]=(i-1)/block+1;
    for(int i=1;i<=n;i++) d[i]=a[i];
    for(int i=1;i<=num;i++) sort(d+l[i],d+r[i]+1);
}
void update(int pos,int w){
	a[pos]=w;
	for(int i=l[belong[pos]];i<=r[belong[pos]];i++) d[i]=a[i];
	sort(d+l[belong[pos]],d+r[belong[pos]]+1);
}
int ask(int L,int R,int W){
    int ans = 0;
    if(belong[L]==belong[R]){
        for(int i=L;i<=R;i++){
        	if(a[i]<W) ans++;
		}
        return ans;
    }
    for(int i=L;i<=r[belong[L]];i++){
    	if(a[i]<W) ans++;
	}
    for(int i=l[belong[R]];i<=R;i++){
    	if(a[i]<W) ans++;
	}
    for(int i=belong[L]+1;i<belong[R];i++){
        int ll=l[i],rr=r[i],Ans=0;
        while(ll<=rr){
            int mid=(ll+rr)/2;
            if(d[mid]<W) ll=mid+1,Ans=mid-l[i]+1;
            else rr=mid-1;
        }
        ans+=Ans;
    }
    return ans;
}
int main(){
//	freopen("input.txt","r",stdin);
    scanf("%d%d%d",&n,&m,&u);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    build();
    for(int i=1;i<=m;i++){
    	int L,R,x,y;
		scanf("%d%d%d%d",&L,&R,&x,&y);
		int ans=ask(L,R,x);
		update(y,(LL)u*ans/(R-L+1));
    }
    for(int i=1;i<=n;i++) printf("%d\n",a[i]);
}

思路

分块水题
注意u*ans会爆LL

本文标题:蓝书 嵌套+分块

文章作者:Hippopmonkey

发布时间:2017-10-02, 22:06:09

最后更新:2017-10-03, 19:38:51

原始链接:http://xuboming8.github.io/2017/10/02/蓝书-嵌套-分块/

许可协议: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。

文章目录
  1. 1. 蓝书 嵌套+分块
    1. 1.1. uva 11297
      1. 1.1.1. 题目要求
      2. 1.1.2. 参考AC代码
      3. 1.1.3. 思路
    2. 1.2. uva 11990
      1. 1.2.1. 题目要求
      2. 1.2.2. 参考AC代码(树状数组+BST)
      3. 1.2.3. 参考AC代码(树状数组+cdq分治)
      4. 1.2.4. 思路
    3. 1.3. uva 12003
      1. 1.3.1. 题目要求
      2. 1.3.2. 参考AC代码
      3. 1.3.3. 思路
|