数列分块1-9

发表于 | 分类于 ， |
这是关于分块的9道题目

数列分块1-9

偷下懒QuQ

题目链接

loj的数列分块如门1-9

这算是题解了吧

题解的话
我就不说了吧
毕竟，黄学长的博客里已经说得
很清楚了
吧2333(我真是废QAQ
………Hzwer传送门

代码

数列分块1

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
#include<cmath>
#include<cstdio>
#include<cstring>
#include<algorithm>
int n,m;
inline int read() {	
	int x=0,f=1;
	char c=getchar();
	while(c<'0'||c>'9') {if(c=='0')f=-1;c=getchar();}
	while(c<='9'&&c>='0')x=x*10+c-'0',c=getchar();
	return x*f;
}
const int maxn = 100007;
int a[maxn],bl[maxn],tag[maxn],size;
void modify(int aa,int b,int c) {
	for(int i=aa;i<=std::min(bl[aa]*size,b);++i) a[i]+=c;
	if(bl[aa]!=bl[b])
		for(int i=(bl[b]-1)*size+1;i<=b;++i)a[i]+=c;
	for(int i=bl[aa]+1;i<=bl[b]-1;++i) tag[i]+=c;
}
int main()  {
	n=read(),size=sqrt(n);
	for(int i=1;i<=n;++i) a[i]=read();
	for(int i=1;i<=n;++i) bl[i]=(i-1)/size+1;
	for(int  op,aa,b,c,i=1;i<=n;++i) {
		op=read(),aa=read(),b=read(),c=read();
		if(!op)modify(aa,b,c);
		else printf("%d\n",a[b]+tag[bl[b]]);
	}
	return 0;
}

数列分块2

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
#include<cmath>
#include<vector>
#include<cstdio>
#include<cstring>
#include<algorithm>
using std::vector;
vector<int>vec[100086];
int n,m;
inline int read() {	
	int x=0,f=1;
	char c=getchar();
	while(c<'0'||c>'9') {if(c=='0')f=-1;c=getchar();}
	while(c<='9'&&c>='0')x=x*10+c-'0',c=getchar();
	return x*f;
}
const int maxn = 100007;
int a[maxn],bl[maxn],tag[maxn],size;
void update(int x) {
	vec[x].clear();
	for(int i=(x-1)*size+1;i<=std::min(x*size,n);++i)
		vec[x].push_back(a[i]);
	std::sort(vec[x].begin(),vec[x].end());
}
void modify(int aa,int b,int c) {
	for(int i=aa;i<=std::min(bl[aa]*size,b);++i) a[i]+=c;
	update(bl[aa]);
	if(bl[aa]!=bl[b]) {
		for(int i=(bl[b]-1)*size+1;i<=b;++i)a[i]+=c;
		update(bl[b]);
	}
	for(int i=bl[aa]+1;i<=bl[b]-1;++i) tag[i]+=c;
}
int query(int aa,int b,int c) {
	int ans=0;c*=c;
	for(int i=aa;i<=std::min(b,bl[aa]*size);++i) 
		if(a[i]+tag[bl[aa]]<c)ans++;
	if(bl[aa]!=bl[b]) 
		for(int i=(bl[b]-1)*size+1;i<=b;++i)
			if(a[i]+tag[bl[b]]<c)ans++;
	for(int i=bl[aa]+1;i<=bl[b]-1;++i) {
		int x=c-tag[i];
		ans+=lower_bound(vec[i].begin(),vec[i].end(),x)-vec[i].begin();
	}
	return ans;
}
int main()  {
	n=read(),size=sqrt(n);
	for(int i=1;i<=n;++i) a[i]=read();
	for(int i=1;i<=n;++i) bl[i]=((i-1)/size+1),vec[bl[i]].push_back(a[i]);
    for(int i=1;i<=bl[n];i++)std::sort(vec[i].begin(),vec[i].end());	
	for(int  op,aa,b,c,i=1;i<=n;++i) {
		op=read(),aa=read(),b=read(),c=read();
		if(!op)modify(aa,b,c);
		else printf("%d\n",query(aa,b,c));
	}
	return 0;
}

数列分块3

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
#include<cmath>
#include<vector>
#include<cstdio>
#include<cstring>
#include<algorithm>
using std::vector;
vector<int>vec[100086];
int n,m;
inline int read() {	
	int x=0,f=1;
	char c=getchar();
	while(c<'0'||c>'9') {if(c=='0')f=-1;c=getchar();}
	while(c<='9'&&c>='0')x=x*10+c-'0',c=getchar();
	return x*f;
}
const int maxn = 100007;
int a[maxn],bl[maxn],tag[maxn],size;
void update(int x) {
	vec[x].clear();
	for(int i=(x-1)*size+1;i<=std::min(x*size,n);++i)
		vec[x].push_back(a[i]);
	std::sort(vec[x].begin(),vec[x].end());
}
void modify(int aa,int b,int c) {
	for(int i=aa;i<=std::min(bl[aa]*size,b);++i) a[i]+=c;
	update(bl[aa]);
	if(bl[aa]!=bl[b]) {
		for(int i=(bl[b]-1)*size+1;i<=b;++i)a[i]+=c;
		update(bl[b]);
	}
	for(int i=bl[aa]+1;i<=bl[b]-1;++i) 
		tag[i]+=c;
}
int query(int aa,int b,int c) {
	int tmp,ret=-1,retc=0x3f3f3f3f;
	for(int i=aa;i<=std::min(b,bl[aa]*size);++i) 
		if(c>a[i]+tag[bl[aa]]) {
			tmp=(c-(a[i]+tag[bl[aa]]));
			if(tmp<retc) retc=tmp,ret=a[i]+tag[bl[aa]];
		}
		//if(a[i]+tag[bl[aa]]>=c)return a[i-1];
	if(bl[aa]!=bl[b]) 
		for(int i=(bl[b]-1)*size+1;i<=b;++i)
			if(c>a[i]+tag[bl[b]]) {
				tmp=(c-(a[i]+tag[bl[b]]));
				if(tmp<retc) retc=tmp,ret=a[i]+tag[bl[b]];
			}
	for(int i=bl[aa]+1;i<=bl[b]-1;++i) {
		int x=c-tag[i];
		int loc=lower_bound(vec[i].begin(),vec[i].end(),x)-vec[i].begin()-1;
		if(loc<0)continue;
		tmp=c-vec[i][loc]-tag[i];
		if(tmp<retc) retc=tmp,ret=vec[i][loc]+tag[i];
	}
	return ret;
}
int main()  {
	//std::cin>>a;std::cout<<a;
	n=read(),size=sqrt(n);
	for(int i=1;i<=n;++i) a[i]=read();
	for(int i=1;i<=n;++i) bl[i]=((i-1)/size+1),vec[bl[i]].push_back(a[i]);
    for(int i=1;i<=bl[n];i++)std::sort(vec[i].begin(),vec[i].end());	
	for(int  op,aa,b,c,i=1;i<=n;++i) {
		op=read(),aa=read(),b=read(),c=read();
		if(!op)modify(aa,b,c);
		else printf("%d\n",query(aa,b,c));
	}
	return 0;
}
/*
6
123 321 245 654 232 233
1 2 5 246
0 2 4 666
1 1 6 888
*/

数列分块4

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
#include<cmath>
#include<vector>
#include<cstdio>
#include<cstring>
#include<algorithm>
int n,m;
inline int read() {	
	int x=0,f=1;
	char c=getchar();
	while(c<'0'||c>'9') {if(c=='0')f=-1;c=getchar();}
	while(c<='9'&&c>='0')x=x*10+c-'0',c=getchar();
	return x*f;
}
const int maxn = 100007;
long long  a[maxn];int bl[maxn],size;
long long tag[maxn],sum[maxn];
void modify(int aa,int b,int c) {
	for(int i=aa;i<=std::min(bl[aa]*size,b);++i) a[i]+=c,sum[bl[i]]+=c;//,[bl[a]]+=c;
	if(bl[aa]!=bl[b]) 
		for(int i=(bl[b]-1)*size+1;i<=b;++i) a[i]+=c,sum[bl[i]]+=c;//,tag[bl[b]]+=c;
	for(int i=bl[aa]+1;i<=bl[b]-1;++i) 
		tag[i]+=c;
}
long long  query(int aa,int b,int c) {
	long long ans=0;
	for(int i=aa;i<=std::min(b,bl[aa]*size);++i) 
		ans+=a[i]+tag[bl[aa]];
	if(bl[aa]!=bl[b]) 
		for(int i=(bl[b]-1)*size+1;i<=b;++i)
			ans+=a[i]+tag[bl[b]];
	for(int i=bl[aa]+1;i<=bl[b]-1;++i) {
		ans+=sum[i]+tag[i]*size;
	}
	return ans%c;
}
int main()  {
	//std::cin>>a;std::cout<<a;
	n=read(),size=sqrt(n);
	for(int i=1;i<=n;++i) a[i]=read();
	for(int i=1;i<=n;++i) bl[i]=((i-1)/size+1),sum[bl[i]]+=a[i];
	for(int  op,aa,b,c,i=1;i<=n;++i) {
		op=read(),aa=read(),b=read(),c=read();
		if(!op)modify(aa,b,c);
		else printf("%d\n",query(aa,b,c+1));
	}
	return 0;
}
/*
6
123 321 245 654 232 233
1 2 5 246
0 2 4 666
1 1 6 888
*/

数列分块5

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
#include<cmath>
#include<cstdio>
#include<algorithm>
using std::min;
inline int read() {
    int  x=0,op=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')op=-1;c=getchar();}
    while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();
    return x*op;
}
const int maxn = 100007;
int n,size;
int bl[maxn],a[maxn],sum[maxn],tag[maxn];
inline void update(int x) {
    if(tag[x])return;
    tag[x]=1,sum[x]=0;
    for(int i=(x-1)*size+1;i<=x*size;i++) {
        a[i]=sqrt(a[i]),sum[x]+=a[i];
        if(a[i]>1)tag[x]=0;
    }
}
void add(int l,int r) {
    for(int i=l;i<=min(bl[l]*size,r);i++)
        sum[bl[l]]-=a[i],a[i]=sqrt(a[i]),sum[bl[l]]+=a[i];
    if(bl[l]!=bl[r])
        for(int i=(bl[r]-1)*size+1;i<=r;i++)
            sum[bl[r]]-=a[i],a[i]=sqrt(a[i]),sum[bl[r]]+=a[i];
    for(int i=bl[l]+1;i<=bl[r]-1;i++)
        update(i);
}
int query(int l,int r) {
    int ans=0;
    for(int i=l;i<=min(bl[l]*size,r);i++) ans+=a[i];
    if(bl[l]!=bl[r])
        for(int i=(bl[r]-1)*size+1;i<=r;i++)
            ans+=a[i];
    for(int i=bl[l]+1;i<=bl[r]-1;i++)
        ans+=sum[i];
    return ans;
}
int main() {
    n=read();size=sqrt(n);
    for(int i=1;i<=n;i++)a[i]=read();
    for(int i=1;i<=n;i++) 
        bl[i]=(i-1)/size+1,sum[bl[i]]+=a[i];
    for(int op,a,b,c,i=1;i<=n;i++) {
        op=read(),a=read(),b=read(),c=read();
        if(!op)add(a,b);
		else printf("%d\n",query(a,b));
    }
    return 0;
}

数列分块6

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
#include<cmath>
#include<vector>
#include<cstdio>
#include<algorithm>
using std::vector;
const int maxn = 100007;
inline int read() {
	int x=0,f=1;char c=getchar();
	while(c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while(c<='9'&&c>='0') x=x*10+c-'0',c=getchar();
	return x*f;
}
vector<int>vec[maxn];
int a[maxn],bl[maxn],size,n;
void insert(int loc,int w) {
	for(int i=1;i<=bl[n];++i) {
		if(loc<=vec[i].size()) {vec[i].insert(vec[i].begin()+loc-1,w);return;}
		loc-=vec[i].size();
	}
}
int query(int loc) {
	for(int i=1;i<=bl[n];++i) {
		if(loc<=vec[i].size()) return vec[i][loc-1];
		loc-=vec[i].size();
	}
}
int main() {
	n=read();size=sqrt(n);
	for(int i=1;i<=n;++i)a[i]=read();
	for(int i=1;i<=n;++i)bl[i]=(i-1)/size+1,vec[bl[i]].push_back(a[i]);
	for(int op,aa,b,c,i=1;i<=n;++i) {
		op=read(),aa=read(),b=read(),c=read();
		if(!op) insert(aa,b);
		else printf("%d\n",query(b));
	}
}

数列分块7

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
#include<cmath>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define mod 10007
using std::min;
const int maxn = 100007;
inline int read() {
	int x=0,f=1;char c=getchar();
	while(c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while(c<='9'&&c>='0') x=x*10+c-'0',c=getchar();
	return x*f;
}
int tagm[maxn],taga[maxn];
int a[maxn],bl[maxn],size,n;
void reset(int x) {
    for(int i=(x-1)*size+1;i<=min(n,x*size);i++)
        a[i]=(a[i]*tagm[x]+taga[x])%mod;
    taga[x]=0;tagm[x]=1;
}
void Modify_Add(int l,int r,int w) {
	reset(bl[l]);
	for(int i=l;i<=min(r,bl[l]*size);++i) a[i]+=w,a[i]%=mod;
	if(bl[l]!=bl[r]) {
		reset(bl[r]);
		for(int i=(bl[r]-1)*size+1;i<=r;++i) 
			a[i]+=w,a[i]%=mod;
	}
	for(int i=bl[l]+1;i<=bl[r]-1;++i) 
		taga[i]+=w,taga[i]%=mod;
}
void Modify_Mul(int l,int r,int w)  {
	reset(bl[l]);
	for(int i=l;i<=min(bl[l]*size,r);++i) a[i]*=w,a[i]%=mod;
	if(bl[l]!=bl[r]) {
		reset(bl[r]);
		for(int i=(bl[r]-1)*size+1;i<=r;++i) 
			a[i]*=w,a[i]%=mod;
	}
	for(int i=bl[l]+1;i<=bl[r]-1;++i) 
		tagm[i]=tagm[i]*w%mod,taga[i]=taga[i]*w%mod;
}
int main() {
	n=read();size=sqrt(n);
	for(int i=1;i<=n;++i)a[i]=read(),tagm[i]=1;tagm[n+1]=1;
	for(int i=1;i<=n;++i)bl[i]=(i-1)/size+1;
	for(int op,aa,b,c,i=1;i<=n;++i) {
		op=read(),aa=read(),b=read(),c=read()%mod;
		if(!op) Modify_Add(aa,b,c);
		else if(op==1)Modify_Mul(aa,b,c);
		else printf("%d\n",(a[b]*tagm[bl[b]]+taga[bl[b]])%mod);
	}
	return 0;
}

数列分块8

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
#include<cmath>
#include<cstdio>
#include<cstring>
#include<algorithm>
using std::min;
const int maxn = 100007;
inline int read() {
	int x=0,f=1;
	char c=getchar();
	while(c<'0'||c>'9') {
		if(c=='-')f=-1;
		c=getchar();
	}while(c<='9'&&c>='0') x=x*10+c-'0',c=getchar();
	return x*f;
}
int n,a[maxn],bl[maxn],tag[maxn],ans=0,size;
void solve(int l,int r,int c) {
	ans=0;
	if(tag[bl[l]]!=-1) {
		for(int i=(bl[l]-1)*size+1;i<=bl[l]*size;++i) 
			a[i]=tag[bl[l]];
		tag[bl[l]]=-1;
		}
	for(int i=l;i<=min(bl[l]*size,r);++i)
	ans+=a[i]==c,a[i]=c;
	//tag[bl[r]]=-1;
	if(bl[l]!=bl[r]) {
		if(tag[bl[r]]!=-1) { 
			for(int i=(bl[r]-1)*size+1;i<=bl[r]*size;++i) 
				a[i]=tag[bl[r]];
			tag[bl[r]]=-1;
			}
		for(int i=(bl[r]-1)*size+1;i<=r;++i)
			ans+=a[i]==c,a[i]=c;
	}
	for(int i=bl[l]+1;i<=bl[r]-1;++i) {
		if(tag[i]==c)ans+=size;
		else if(tag[i]==-1) {
			for(int j=(i-1)*size+1;j<=i*size;++j) 
				ans+=a[j]==c,a[j]=c;
			tag[i]=c;
		}
		else tag[i]=c;
	}
	printf("%d\n",ans);
}
int main() {
	n=read();size=sqrt(n);
	memset(tag,-1,sizeof tag);
	for(int i=1;i<=n;++i)a[i]=read();
	for(int i=1;i<=n;++i)bl[i]=(i-1)/size+1;
	for(int aa,b,c,i=1;i<=n;++i) {
		aa=read(),b=read(),c=read();
		solve(aa,b,c);
	}
	return 0;
}

数列分块9

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
#include<map>
#include<cmath>
#include<vector>
#include<cstdio>
#include<cstring>
#include<algorithm>
using std::map;
using std::vector;
inline int read() {
    int x=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();
    return x*f;
}
const int maxn = 110007;
int v[maxn],val[maxn];
int n,size,bl[maxn],id=0,atmp[671][671],cnt[10086];
vector<int>vec[1007];
map<int,int>mp;
void build(int x) {
    memset(cnt,0,sizeof cnt);
    int mcnt=0,mans=0; 
    for(int i=(x-1)*size+1;i<=n;++i) {
        int vu=v[i]; 
        cnt[vu]++;
        if(mcnt<cnt[vu]||(mcnt==cnt[vu]&&val[vu]<val[mans])) 
            mans=vu,mcnt=cnt[vu];
        atmp[x][bl[i]]=mans;
    }
}
inline int count(int a,int b,int mans) {
    return upper_bound(vec[mans].begin(),vec[mans].end(),b)-lower_bound(vec[mans].begin(),vec[mans].end(),a);
}
int query(int a,int b) {
    int mans=atmp[bl[a]+1][bl[b]-1]; 
    int mcnt=count(a,b,mans);
    for(int i=a;i<=std::min(bl[a]*size,b);++i) {
        int qcnt=count(a,b,v[i]);if(qcnt>mcnt||(qcnt==mcnt&&val[v[i]]<val[mans])) mcnt=qcnt,mans=v[i];
    }
    if(bl[a]!=bl[b]) 
        for(int i=(bl[b]-1)*size;i<=b;++i) {
            int qcnt=count(a,b,v[i]);if(qcnt>mcnt||(qcnt==mcnt&&val[v[i]]<val[mans])) mcnt=qcnt,mans=v[i];
        }
    return val[mans];
}   
int main() {
    n=read();size=sqrt(n);
    for(int i=1;i<=n;++i) {
        v[i]=read();
        if(!mp[v[i]]) 
            mp[v[i]]=++id,val[id]=v[i];
        v[i]=mp[v[i]];
        vec[v[i]].push_back(i);
    }
    for(int i=1;i<=n;++i) bl[i]=(i-1)/size+1;
    for(int i=1;i<=bl[n];++i)build(i);
    for(int a,b,i=1;i<=n;++i) {
        a=read(),b=read();
		if(a>b)std::swap(a,b);
        printf("%d\n",query(a,b));
    }
    return 0;
}

完~