分块专题一

自用笔记算法

分块专题一

bzoj 3343

题目要求

区间初始值ai 给出两种操作
区间l到r内加w
区间l到r内询问大于等于w的个数

参考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
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1000006;
int n,m,num,belong[maxn],block,l[maxn],r[maxn],a[maxn],p[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);
}
char op[5];
int A,B,C;
void update(int L,int R,int W){
    if(belong[L]==belong[R]){
        for(int i=l[belong[L]];i<=r[belong[R]];i++) a[i]+=p[belong[L]];
        p[belong[L]]=0;
        for(int i=L;i<=R;i++) a[i]+=W;
        for(int i=l[belong[L]];i<=r[belong[R]];i++) d[i]=a[i];
        sort(d+l[belong[L]],d+r[belong[R]]+1);
        return;
    }
    for(int i=l[belong[L]];i<=r[belong[L]];i++) a[i]+=p[belong[L]];
    p[belong[L]]=0;
    for(int i=L;i<=r[belong[L]];i++) a[i]+=W;
    for(int i=l[belong[L]];i<=r[belong[L]];i++) d[i]=a[i];
    sort(d+l[belong[L]],d+r[belong[L]]+1);
//~~~~~~~~~~~~~~~~~
    for(int i=l[belong[R]];i<=r[belong[R]];i++) a[i]+=p[belong[R]];
    p[belong[R]]=0;
    for(int i=l[belong[R]];i<=R;i++) a[i]+=W;
    for(int i=l[belong[R]];i<=r[belong[R]];i++) d[i]=a[i];
    sort(d+l[belong[R]],d+r[belong[R]]+1);
//~~~~~~~~~~~~~~~~~
    for(int i=belong[L]+1;i<belong[R];i++) p[i]+=W;
}
void 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]+p[belong[i]]>=W) ans++;
		}
        printf("%d\n",ans);
        return;
    }
    for(int i=L;i<=r[belong[L]];i++){
    	if(a[i]+p[belong[i]]>=W) ans++;
	}
    for(int i=l[belong[R]];i<=R;i++){
    	if(a[i]+p[belong[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]+p[i]>=W) rr=mid-1,Ans=r[i]-mid+1;
            else ll=mid+1;
        }
        ans+=Ans;
    }
    printf("%d\n",ans);
}
int main(){
//	freopen("input.txt","r",stdin);
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    build();
    for(int i=1;i<=m;i++){
        scanf("%s%d%d%d",&op,&A,&B,&C);
        if(op[0]=='A') ask(A,B,C);
        else update(A,B,C);
    }
}

思路

num：分块的个数
belong[i]：表示i属于哪一块
block：表示块的大小
l[i]：表示i这块的左端点位置
r[i]：表示右端点位置
数组p相当于lazy 每个块内排序 最后完整的块用二分找到大于等于w的位置
当区间修改的端点经过了不完整的区间 这一段的lazy要加到a上 并更新到d上 因为lazy代表的是这一整块的延迟标记

bzoj 4636

题目要求

蒟蒻DCrusher不仅喜欢玩扑克，还喜欢研究数列
题目描述
DCrusher有一个数列，初始值均为0，他进行N次操作，每次将数列[a,b）这个区间中所有比k小的数改为k，他想知
道N次操作后数列中所有元素的和。他还要玩其他游戏，所以这个问题留给你解决。

参考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
#include<bits/stdc++.h>
#define maxn 80050
#define lson rt<<1,l,mid
#define rson rt<<1|1,mid+1,r
#define LL long long
#define mm(a,b) memset(a,b,sizeof(a))
using namespace std;
vector<int>v;
int getid(int x){return lower_bound(v.begin(),v.end(),x)-v.begin()+1;}
int sum[maxn],lazy[maxn<<2]; 
struct node{
	int l,r,k;
}a[maxn];
void push_down(int rt){
	lazy[rt<<1]=max(lazy[rt<<1],lazy[rt]);
	lazy[rt<<1|1]=max(lazy[rt<<1|1],lazy[rt]);
} 
void update(int rt,int l,int r,int L,int R,int val){
	if(l>=L && r<=R){
		lazy[rt]=max(lazy[rt],val);
		return;
	}
	push_down(rt);
	int mid=(l+r)>>1;
	if(mid>=L) update(lson,L,R,val);
	if(mid<R) update(rson,L,R,val);
}
LL query(int rt,int l,int r){
	if(l==r) return 1ll*sum[l]*lazy[rt];
	push_down(rt);
	int mid=(l+r)>>1;
	return query(lson)+query(rson);	
}
int main(){
//	freopen("input.txt","r",stdin);
	int n;
	scanf("%d",&n);
	mm(sum,0),mm(lazy,0);
	for(int i=1;i<=n;i++){
		scanf("%d%d%d",&a[i].l,&a[i].r,&a[i].k);
		v.push_back(a[i].l);
		v.push_back(a[i].r);
	}
	sort(v.begin(),v.end());
	v.erase(unique(v.begin(),v.end()),v.end());
	int len=v.size();
	for(int i=0;i<len-1;i++) sum[i+1]=v[i+1]-v[i];
	for(int i=1;i<=n;i++){
		int L=getid(a[i].l);
		int R=getid(a[i].r)-1;
		int k=a[i].k;
		update(1,1,len-1,L,R,k);
	}
	printf("%lld\n",query(1,1,len-1));
	return 0;
}

思路

这题这可以用分块做 但还是采用离散+离线线段树处理
区间范围1e9所以需要离散化
sum维护离散化后每个点与后一个点的差 实际维护的是该段lazy的区间长度
注意是左闭右开的区间 所以R需要-1
还需主要vector下标从0开始 所以计算sum的时候需要后移一位

bzoj 2002

题目要求

某天，Lostmonkey发明了一种超级弹力装置，为了在他的绵羊朋友面前显摆，他邀请小绵羊一起玩个游戏。游戏一开始，Lostmonkey在地上沿着一条直线摆上n个装置，
每个装置设定初始弹力系数ki，当绵羊达到第i个装置时，它会往后弹ki步，达到第i+ki个装置，若不存在第i+ki个装置，则绵羊被弹飞。绵羊想知道当它从第i个装置起步时，
被弹几次后会被弹飞。为了使得游戏更有趣，Lostmonkey可以修改某个弹力装置的弹力系数，任何时候弹力系数均为正整数。

第一行包含一个整数n，表示地上有n个装置，装置的编号从0到n-1,接下来一行有n个正整数，依次为那n个装置的初始弹力系数。第三行有一个正整数m，接下来m行每行
至少有两个数i、j，若i=1，你要输出从j出发被弹几次后被弹飞，若i=2则还会再输入一个正整数k，表示第j个弹力装置的系数被修改成k。对于20%的数据n,m<=10000，
对于100%的数据n<=200000,m<=100000

对于每个i=1的情况，你都要输出一个需要的步数，占一行。

参考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
#include<bits/stdc++.h>
#define maxn 100050
#define LL long long
#define mm(a,b) memset(a,b,sizeof(a))
using namespace std;
int n,q,block,num;
int a[maxn],belong[maxn];
int cnt[maxn],End[maxn];
int l[1100],r[1100];
inline LL read(){
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
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=n;i>=1;i--){
		if(a[i]+i>n) cnt[i]=1,End[i]=-1;
		else if(belong[i]==belong[a[i]+i]) cnt[i]=cnt[i+a[i]]+1,End[i]=End[i+a[i]];
		else cnt[i]=1,End[i]=i+a[i];
	}
}
void update(int x,int y){
	a[x]=y;
	for(int i=x;i>=l[belong[x]];i--){
		if(a[i]+i>n) cnt[i]=1,End[i]=-1;
		else if(belong[i]==belong[a[i]+i]) cnt[i]=cnt[i+a[i]]+1,End[i]=End[i+a[i]];
		else cnt[i]=1,End[i]=i+a[i];
	}
}
int solve(int x){
	int ans=0;
	while(1){
		ans+=cnt[x];
		if(End[x]<0) break;
		x=End[x];
	}
	return ans;
}
int main(){
//	freopen("input.txt","r",stdin);
	n=read();
	for(int i=1;i<=n;i++) a[i]=read();
	build();
	q=read();
	while(q--){
		int op; op=read();
		if(op==1){
			int x; x=read();
			x++;
			printf("%lld\n",solve(x));
		}
		else{
			int x,y;
			x++; 
			x=read(),y=read();
			update(x,y);
		}
	}
	return 0;
}

思路

分块
cnt维护跳出该块的步数
end维护跳到下一个块的位置
注意下标从0开始 x需要++

cf 444c

题目要求

开始,a[i]=i,b[i]=0
然后两个操作
1.使得[l,r]的b[i]+=fabs(x-a[i]),a[i]=x
2.查询[l,r]的b[i]和

参考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
#include<bits/stdc++.h>
using namespace std;  
#define ll long long  
#define L(x) (x<<1)  
#define R(x) (x<<1|1)  
#define N 100005  
inline int Mid(int a,int b){return (a+b)>>1;}  
inline ll ABS(ll x){return x>0?x:-x;}  
int n,m;  
struct node{  
    int l, r, id;  
    ll siz(){return (ll)(r-l+1);}  
    ll sum, col, lazy, same;  
}tree[N<<2];  
void push_down(int id){   
    if(tree[id].lazy) {  
        tree[L(id)].sum += tree[L(id)].siz()*tree[id].lazy;  
        tree[R(id)].sum += tree[R(id)].siz()*tree[id].lazy;  
        tree[L(id)].lazy += tree[id].lazy;  
        tree[R(id)].lazy += tree[id].lazy;  
        tree[id].lazy = 0;  
    }  
    if(tree[id].col>=0){  
        tree[L(id)].col = tree[R(id)].col = tree[id].col;  
    }  
}  
void push_up(int id){  
    if(tree[L(id)].col==tree[R(id)].col&&tree[L(id)].col>=0)  
    tree[id].col = tree[L(id)].col, tree[id].same = 1;  
    else tree[id].col = -1, tree[id].same = 0;  
    tree[id].sum = tree[L(id)].sum+tree[R(id)].sum;  
}  
void build(int l, int r, int id){  
    tree[id].l = l, tree[id].r = r;  
    tree[id].sum = 0;  
    tree[id].lazy = 0;  
    tree[id].col = -1;  
    tree[id].same = 0;  
    if(l==r){  
        tree[id].col = l;  
        tree[id].same = 1;  
        return ;  
    }  
    int mid = Mid(l,r);  
    build(l,mid,L(id));  
    build(mid+1,r,R(id));  
}  
void updata(int l, int r, int id, ll col){  
    if(l==tree[id].l&&tree[id].r==r && tree[id].same){  
        tree[id].sum += tree[id].siz() * ABS(col-tree[id].col);  
        tree[id].lazy += ABS(col-tree[id].col);  
        tree[id].col = col;  
        return ;  
    }  
    push_down(id);  
    int mid = Mid(tree[id].l, tree[id].r);  
    if(mid<l) updata(l,r,R(id),col);  
    else if(r<=mid) updata(l,r,L(id),col);  
    else updata(l,mid,L(id),col),updata(mid+1,r,R(id),col);    
    push_up(id);  
}  
ll query(int l, int r, int id){  
    if(l==tree[id].l && tree[id].r==r) return tree[id].sum;  
    push_down(id);  
    int mid = Mid(tree[id].l, tree[id].r);  
    if(mid<l) return query(l,r,R(id));  
    else if(r<=mid) return query(l,r,L(id));  
    else return query(l,mid,L(id))+query(mid+1,r,R(id));  
}  
int main(){
//	freopen("input.txt","r",stdin);
    int type, l, r;  
    ll x;  
    while(~scanf("%d %d",&n,&m)){  
        build(1,n,1);  
        while(m--){  
            scanf("%d %d %d",&type,&l,&r);  
            if(type==1){  
                scanf("%lld",&x);  
                updata(l,r,1,x);  
            }  
            else {  
                printf("%lld\n",query(l,r,1));  
            }  
        }  
    }  
    return 0;  
}

思路

可以用分块做 本题采用线段树 但用了分块的思想
same表示区间的颜色是否相同 0表示不同
每次更新的时候找到颜色相同的块更新

bzoj 2120

题目要求

墨墨购买了一套N支彩色画笔（其中有些颜色可能相同），摆成一排，你需要回答墨墨的提问。墨墨会像你发布如下指令：
1、 Q L R代表询问你从第L支画笔到第R支画笔中共有几种不同颜色的画笔。 2、 R P Col 把第P支画笔替换为颜色Col。
为了满足墨墨的要求，你知道你需要干什么了吗？

第1行两个整数N，M，分别代表初始画笔的数量以及墨墨会做的事情的个数。第2行N个整数，分别代表初始画笔排中第i支画笔的颜色。
第3行到第2+M行，每行分别代表墨墨会做的一件事情，格式见题干部分。

对于每一个Query的询问，你需要在对应的行中给出一个数字，代表第L支画笔到第R支画笔中共有几种不同颜色的画笔。

参考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
#include<bits/stdc++.h>
#define maxn 2000005
#define mm(a,b) memset(a,b,sizeof(a))
using namespace std;
int block,num,n,q;
int l[maxn],r[maxn],belong[maxn];
int c[maxn],last[maxn],b[maxn],a[maxn];
void build(){
    block=(int)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++){
		b[i]=last[c[i]];
		last[c[i]]=i;
	}
	for(int i=1;i<=n;i++) a[i]=b[i];
    for(int i=1;i<=num;i++) sort(a+l[i],a+r[i]+1);
}
void update(int x,int y){
	for(int i=1;i<=n;i++) last[c[i]]=0;
	c[x]=y;
	for(int i=1;i<=n;i++){
		int temp=b[i];
		b[i]=last[c[i]];
		if(temp!=b[i]){
			for(int j=l[belong[i]];j<=r[belong[i]];j++) a[j]=b[j];
			sort(a+l[belong[i]],a+r[belong[i]]+1);
		}
		last[c[i]]=i;
	}
} 
int ask(int x,int y){
	int ans=0;
	if(belong[x]==belong[y]){
		for(int i=x;i<=y;i++){
			if(b[i]<x) ans++;
		}
		return ans;
	}
	for(int i=x;i<=r[belong[x]];i++){
		if(b[i]<x) ans++;
	}
	for(int i=l[belong[y]];i<=y;i++){
		if(b[i]<x) ans++;
	}
	for(int i=belong[x]+1;i<belong[y];i++){
		int le=l[i],ri=r[i];
		int fi=le,re=0;
		while(le<=ri){
			int mid=(le+ri)>>1;
			if(a[mid]<x) re=mid,le=mid+1;
			else ri=mid-1;
		}
		ans+=re-fi+1;
	}
	return ans;
}
int main(){
//	freopen("input.txt","r",stdin);
	scanf("%d%d",&n,&q);
	for(int i=1;i<=n;i++) scanf("%d",&c[i]);
	build();
	while(q--){
		char ch[5];
		int x,y;
		scanf("%s%d%d",ch,&x,&y);
		if(ch[0]=='Q') printf("%d\n",ask(x,y));
		else update(x,y);
	}
	return 0;
}

思路

分块
也可以用线段树 参考muti多校4
数组c表示颜色 数组b记录每一个位置颜色上一次的出现位置 last维护每种颜色的上一次出现位置 a和b相同 用来二分查找
对于每一块 b[i]<l就代表这个数字出现了一次 ans++
更新操作里 temp记录上一次的b[i]值 如果和这次更新的不一样 那么这一段重新更新排序
注意数组要开100w 因为last记录的是颜色

cdoj 1292

题目要求

卿学姐有n个花坛，一开始第i个花坛里有A[i]朵花。每过一段时间，卿学姐都会在花坛里种上新的花。
作为一个聪明的学姐，卿学姐的种花方式也是与众不同 , 每一次，卿学姐会在第x个花坛种上y朵花，然后在第x+1个花坛上种上y−1朵花，
再在第x+2个花坛上种上y−2朵花……以此类推，直到种到最后一个花坛，或者不需要种花为止。
喵哈哈的村民们都喜欢去卿学姐的后院赏花，沈宝宝也不例外。然而沈宝宝可不是省油的灯，怎么可能会老老实实地赏花呢。每次沈宝宝来时，
都会随机询问卿学姐在第i个花坛有多少朵花。

第一行输入两个整数，花坛个数NN和操作次数Q。
第二行NN个整数A[1],A[2],A[3]…A[N] (1≤A[i]≤2^31)
接下来Q行，每行一个操作。
1 x y 表示卿学姐会在x号花坛种y朵花，并按相应的规律在后面的花坛上种花。
2 x 表示沈宝宝问卿学姐第x个花坛有多少朵花。

对于每个询问操作，按顺序输出答案对772002+233取模的值。

参考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
#include<bits/stdc++.h>
#define maxn 10050
#define LL long long
#define mm(a,b) memset(a,b,sizeof(a))
using namespace std;
const int mod = 772002+233;
int block,num,n,q;
int l[maxn],r[maxn],belong[maxn];
LL lazy[maxn],Num[maxn],ed[maxn],a[maxn];
void build(){
    block=(int)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;
}
void update(int x,LL y){
	for(int i=x;i<=r[belong[x]];i++){
		a[i]=(a[i]+y)%mod;
		y--;
		if(y==0) return;
	}
	for(int i=belong[x]+1;i<=num;i++){
		lazy[l[i]]+=y;
		Num[l[i]]++;
		if(y<r[i]-l[i]+1){
			ed[y+l[i]]++;
			break;
		}
		y-=(r[i]-l[i]+1);
	}
} 
LL ask(int x){
	LL add=0,number=0;
	for(int i=l[belong[x]];i<=r[belong[x]];i++){
		add+=lazy[i];
		number+=Num[i];
		number-=ed[i];
		lazy[i]=Num[i]=ed[i]=0;
		a[i]=(a[i]+add)%mod;
		add-=number;
	}
	return a[x]%mod;
}
int main(){
//	freopen("input.txt","r",stdin);
	scanf("%d%d",&n,&q);
	for(int i=1;i<=n;i++) scanf("%lld",&a[i]),a[i]%=mod;
	build();
	while(q--){
		int op;
		scanf("%d",&op);
		if(op==1){
			int x;
			LL y;
			scanf("%d%lld",&x,&y);
			update(x,y);
		}
		else{
			int x;
			scanf("%d",&x);
			printf("%lld\n",ask(x));
		}
	}
	return 0;
}

思路

对于这种乱更新乱询问的 分块暴力即可
散块直接暴力 lazy把延迟标记打在块的左端点上 num记录有多少次更新打在左端点上 ed表示有多少次终止
最后对x所在的区间进行更新 逐位加lazy并减Num 如果碰到ed还要–

HUD 4858

题目要求

我们建造了一个大项目！这个项目有n个节点，用很多边连接起来，并且这个项目是连通的！
两个节点间可能有多条边，不过一条边的两端必然是不同的节点。
每个节点都有一个能量值。
现在我们要编写一个项目管理软件，这个软件呢有两个操作：
1.给某个项目的能量值加上一个特定值。
2.询问跟一个项目相邻的项目的能量值之和。（如果有多条边就算多次，比如a和b有2条边，那么询问a的时候b的权值算2次）

第一行一个整数T(1 <= T <= 3),表示测试数据的个数。
然后对于每个测试数据，第一行有两个整数n(1 <= n <= 100000)和m(1 <= m <= n + 10)，分别表示点数和边数。
然后m行，每行两个数a和b，表示a和b之间有一条边。
然后一个整数Q。
然后Q行，每行第一个数cmd表示操作类型。如果cmd为0，那么接下来两个数u v表示给项目u的能量值加上v(0 <= v <= 100)。
如果cmd为1，那么接下来一个数u表示询问u相邻的项目的能量值之和。
所有点从1到n标号。

对每个询问，输出一行表示答案

参考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
#include<bits/stdc++.h>
#define maxn 100050
#define fi first
#define se second
#define mm(a,b) memset(a,b,sizeof(a))
using namespace std;
vector<int>e[maxn];
pair<int,int>a[maxn];
int n,m,q;
int num[maxn],sum[maxn],cnt[maxn];
void init(){
	for(int i=0;i<=n;i++) e[i].clear();
	mm(a,0),mm(num,0),mm(sum,0),mm(cnt,0);
}
int main(){
//	freopen("input.txt","r",stdin);
	int t;
	scanf("%d",&t);
	while(t--){
		init();
		scanf("%d%d",&n,&m);
		int s=sqrt(m+0.5);
		for(int i=1;i<=m;i++){
			scanf("%d%d",&a[i].fi,&a[i].se);
			cnt[a[i].fi]++,cnt[a[i].se]++;
		}
		for(int i=1;i<=m;i++){
			int u=a[i].fi,v=a[i].se;
			if(cnt[u]<s) e[u].push_back(v);
			if(cnt[v]<s) e[v].push_back(u);
			if(cnt[u]>=s && cnt[v]>=s){
				e[u].push_back(v);
				e[v].push_back(u);
			}
		}
		scanf("%d",&q);
		while(q--){
			int op;
			scanf("%d",&op);
			if(op==1){
				int x;
				scanf("%d",&x);
				if(cnt[x]<s){
					int ans=0;
					int len=e[x].size();
					for(int i=0;i<len;i++){
						int next=e[x][i];
						ans+=num[next];
					}
					printf("%d\n",ans);
				}
				else printf("%d\n",sum[x]);
			}
			else{
				int x,y;
				scanf("%d%d",&x,&y);
				num[x]+=y;
				int len=e[x].size();
				for(int i=0;i<len;i++){
					int next=e[x][i];
					sum[next]+=y;
				}
			}
		}
	}
	return 0;
}

思路

对点的分块
轻点：对于边集小于sqrt(m)的点，我们就直接暴力去加周围的点就好了
重点：对于边集大于sqrt(m)的点，我们就只加与他相邻的重点和轻点对它的贡献
加边时 重点到轻点不需要连边 因为重点已经用sum在与他相邻的重点和轻点时已经算过了
这样我们每次查询的时候，如果查询的是轻点，我们就暴力扫一遍
如果查询的是重点，就输出目前的权值就好了

本文标题:分块专题一

文章作者:Hippopmonkey

发布时间:2017-08-28, 19:39:00

最后更新:2017-10-03, 19:39:27

原始链接:http://xuboming8.github.io/2017/08/28/分块专题/

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

文章目录
  1. 1. 分块专题一
    1. 1.1. bzoj 3343
      1. 1.1.1. 题目要求
      2. 1.1.2. 参考AC代码
      3. 1.1.3. 思路
    2. 1.2. bzoj 4636
      1. 1.2.1. 题目要求
      2. 1.2.2. 参考AC代码
      3. 1.2.3. 思路
    3. 1.3. bzoj 2002
      1. 1.3.1. 题目要求
      2. 1.3.2. 参考AC代码
      3. 1.3.3. 思路
    4. 1.4. cf 444c
      1. 1.4.1. 题目要求
      2. 1.4.2. 参考AC代码
      3. 1.4.3. 思路
    5. 1.5. bzoj 2120
      1. 1.5.1. 题目要求
      2. 1.5.2. 参考AC代码
      3. 1.5.3. 思路
    6. 1.6. cdoj 1292
      1. 1.6.1. 题目要求
      2. 1.6.2. 参考AC代码
      3. 1.6.3. 思路
    7. 1.7. HUD 4858
      1. 1.7.1. 题目要求
      2. 1.7.2. 参考AC代码
      3. 1.7.3. 思路
|