In The End

个人博客

0%

分块(平方分割)算法

发表于 更新于 分类于 ， ，

这篇也是用来记录最近做过的题目的

首先是洛谷的P2801教主的魔法

题目描述

教主最近学会了一种神奇的魔法，能够使人长高。于是他准备演示给XMYZ信息组每个英雄看。于是N个英雄们又一次聚集在了一起，这次他们排成了一列，被编号为1、2、……、N。

每个人的身高一开始都是不超过1000的正整数。教主的魔法每次可以把闭区间[L, R]（1≤L≤R≤N）内的英雄的身高全部加上一个整数W。（虽然L=R时并不符合区间的书写规范，但我们可以认为是单独增加第L（R）个英雄的身高）

CYZ、光哥和ZJQ等人不信教主的邪，于是他们有时候会问WD闭区间 [L, R] 内有多少英雄身高大于等于C，以验证教主的魔法是否真的有效。

WD巨懒，于是他把这个回答的任务交给了你。

输入输出格式

输入格式：

第1行为两个整数N、Q。Q为问题数与教主的施法数总和。

第2行有N个正整数，第i个数代表第i个英雄的身高。

第3到第Q+2行每行有一个操作：

（1） 若第一个字母为“M”，则紧接着有三个数字L、R、W。表示对闭区间 [L, R] 内所有英雄的身高加上W。

（2） 若第一个字母为“A”，则紧接着有三个数字L、R、C。询问闭区间 [L, R] 内有多少英雄的身高大于等于C。

输出格式：

对每个“A”询问输出一行，仅含一个整数，表示闭区间 [L, R] 内身高大于等于C的英雄数。

输入输出样例

输入样例#1：

复制

1
2
3
4
5
6
7
8
9
5 3

1 2 3 4 5

A 1 5 4

M 3 5 1

A 1 5 4

输出样例#1：

复制

1
2
2
3

说明

【输入输出样例说明】

原先5个英雄身高为1、2、3、4、5，此时[1, 5]间有2个英雄的身高大于等于4。教主施法后变为1、2、4、5、6，此时[1, 5]间有3个英雄的身高大于等于4。

【数据范围】

对30%的数据，N≤1000，Q≤1000。

对100%的数据，N≤1000000，Q≤3000，1≤W≤1000，1≤C≤1,000,000,000。

首先这道题我表示写了分块没调函数居然能莽过70分。。。也是尴尬啊！

然后写了一个比较直观暴力的分块优化还是70(还是太暴力了啊啊啊)

分块的暴力就不解释了，我这个update每一次都得排序也是醉了，但是ask的速度还是非常快的了，感觉还是没优化好。。。

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
#include <algorithm>
#include <cstdio>
#include <iostream>
#include <cmath>
using namespace std;
const int maxn=(int)1e6+10;

int block,num,l[maxn],r[maxn],belong[maxn],a[maxn],b[maxn];
int n,m;

int binary(int x,int w){
    int ll=l[x],rr=r[x],mid;
    while(ll<=rr){
        mid=(ll+rr)/2;
        if(b[mid]<w) ll=mid+1;
        else rr=mid-1;
    }
    return r[x]-ll+1;
}

void build(){
    block=(int)sqrt(n)*2;
    num=n/block;
    if(n%block)
        num++;
    for(int i=1;i<=num;i++)
        l[i]=(i-1)*block+1,r[i]=i*block;
    for(int i=1;i<=n;i++)
        belong[i]=(i-1)/block+1;
    for(int i=1;i<=num;i++)
        sort(b+l[i],b+r[i]+1);
}

void update(int left,int right,int val){
    if(belong[left]==belong[right]){
        for(int i=left;i<=right;i++)
            a[i]+=val;
        for(int i=l[belong[left]];i<=r[belong[left]];i++)
            b[i]=a[i];
        sort(b+l[belong[left]],b+r[belong[right]]+1);
    }
    else{
        for(int i=left;i<=r[belong[left]];i++)
            a[i]+=val;
        for(int i=l[belong[left]];i<=r[belong[left]];i++)
            b[i]=a[i];
        sort(b+l[belong[left]],b+r[belong[left]]+1);

        for(int i=belong[left]+1;i<=belong[right]-1;i++)
            for(int j=l[i];j<=r[i];j++)
                a[j]+=val,b[j]+=val;

        for(int i=l[belong[right]];i<=right;i++)
            a[i]+=val;
        for(int i=l[belong[right]];i<=r[belong[right]];i++)
            b[i]=a[i];
        sort(b+l[belong[right]],b+r[belong[right]]+1);
    }
}

int ask(int left,int right,int val){
    int count=0;
    if(belong[left]==belong[right]) {
        for(int i=left;i<=right;i++)
            if(a[i]>=val)
                count++;
    }
    else{
        for(int i=left;i<=r[belong[left]];i++)
            if(a[i]>=val)
                count++;
        for(int i=belong[left]+1;i<=belong[right]-1;i++)
            count+=binary(i,val);
        for(int i=l[belong[right]];i<=right;i++)
            if(a[i]>=val)
                count++;
    }
    return count;
}

int main() {
    while (~scanf("%d%d", &n, &m)) {
        for (int i = 1; i <= n; i++)
            scanf("%d", &a[i]), b[i] = a[i];
        build();
        char ch[3];
        int left, right, val;
        while (m--) {
            scanf("%s%d%d%d", ch, &left, &right, &val);
            if (ch[0] == 'M')
                update(left, right, val);
            else if (ch[0] == 'A')
                printf("%d\n", ask(left, right, val));
        }
        return 0;
    }
}

Super Mario

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 10033 Accepted Submission(s): 4251

Problem Description

Mario is world-famous plumber. His “burly” figure and amazing jumping ability reminded in our memory. Now the poor princess is in trouble again and Mario needs to save his lover. We regard the road to the boss’s castle as a line (the length is n), on every integer point i there is a brick on height hi. Now the question is how many bricks in [L, R] Mario can hit if the maximal height he can jump is H.

Input

The first line follows an integer T, the number of test data.
For each test data:
The first line contains two integers n, m (1 <= n <=10^5, 1 <= m <= 10^5), n is the length of the road, m is the number of queries.
Next line contains n integers, the height of each brick, the range is [0, 1000000000].
Next m lines, each line contains three integers L, R,H.( 0 <= L <= R < n 0 <= H <= 1000000000.)

Output

For each case, output “Case X: “ (X is the case number starting from 1) followed by m lines, each line contains an integer. The ith integer is the number of bricks Mario can hit for the ith query.

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
1
10 10
0 5 2 7 5 4 3 8 7 7 
2 8 6
3 5 0
1 3 1
1 9 4
0 1 0
3 5 5
5 5 1
4 6 3
1 5 7
5 7 3

Sample Output

1
2
3
4
5
6
7
8
9
10
11
Case 1:
4
0
0
3
1
2
0
1
5
1

这道题也是一道分块的裸题，我没有从1开始分块而是改成从0开始分块，不过也不难改，将build里面一些加一减一的值改一改就好了

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 <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;
const int maxn=(int)1e5+10;

int block,num,belong[maxn],l[maxn],r[maxn],b[maxn],origin[maxn];
int n,m;

void build(){
    block=(int)sqrt(n);
    num=n/block;
    if(n%block)
        num++;
    for(int i=0;i<num;i++)
        l[i]=i*block,r[i]=(i+1)*block-1;
    r[num-1]=n;//没-1就runtime error了好几发
    for(int i=0;i<n;i++)
        belong[i]=i/block;
    for(int i=0;i<num;i++)
        sort(b+l[i],b+r[i]+1);
}

int ask(int left,int right,int val){
    int count=0;
    if(belong[left]==belong[right]){
        for(int i=left;i<=right;i++)
            if(origin[i]<=val)
                count++;
    }
    else{
        for(int i=left;i<=r[belong[left]];i++)
            if(origin[i]<=val)
                count++;
        for(int i=belong[left]+1;i<=belong[right]-1;i++)
            count+=(int)(upper_bound(b+l[i],b+r[i]+1,val)-(b+l[i]));
        for(int i=l[belong[right]];i<=right;i++)
            if(origin[i]<=val)
                count++;
    }
    return count;
}

int main(){
    int cas;
    scanf("%d",&cas);
    for(int c=1;c<=cas;c++){
        memset(origin,0,sizeof(origin));
        memset(b,0,sizeof(b));
        scanf("%d%d",&n,&m);
        for(int i=0;i<n;i++)
            scanf("%d", &origin[i]),b[i]=origin[i];
        build();
        int left,right,val;
        printf("Case %d:\n",c);
        while(m--){
            scanf("%d%d%d",&left,&right,&val);
            printf("%d\n",ask(left,right,val));
        }
    }
    return 0;
}