NEFU大一暑假集训-树状数组

题集链接

OP

感谢学长的讲解与付出；

感谢ph和zsl两位大佬的指导与讨论；

夹带私货：
此节课的代表性的内容已经整理到自己的贴子中：【笔记】数据结构

树状数组总的来说可以快速对数组进行单点更改和区间查询（或通过维护前缀实现区间更改和单点查询），适用于一些边改边查的情况；

A Ultra-QuickSort

题目大意

在一个马桶搋子图片的陪同下 求逆序对；
有定义：若 i < j ，且 ai>aja_i\gt a_j ，则构成一对逆序对；

思路

有两种做法，暂且称之为归并法和树状数组法，大体相同，但树状数组法更加直观，具体做法可以参考PPT，下面简述一下归并法；

在归并排序的过程中，我们会得到两个有序递增数组（暂称为a数组和b数组），其中保证左数组（a）的下标均小于右数组（b）；

在通过双指针将两个数组合并时，若对 bjb_j 存在 ai<bj<ai+1a_i\lt b_j\lt a_{i+1}，则说明 a数组中从 ai+1a_{i+1}后的每个数都可以和 bjb_j 构成逆序对；

代码

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
#include <iostream>

using namespace std;
typedef long long ll;
ll a[500005];
ll tmp[500005];
ll ans;
void qs(int l, int r)
{
    if (l == r)
        return;
    int mid = l + r >> 1;
    qs(l, mid);
    qs(mid + 1, r);
    int i = l, j = mid + 1, c = 0;
    while (i <= mid && j <= r)
        if (a[i] <= a[j])
            tmp[c++] = a[i++];
        else
            tmp[c++] = a[j++],ans+=mid-i+1;
    while (i <= mid)
        tmp[c++] = a[i++];
    while (j <= r)
        tmp[c++] = a[j++];
    for (i = l, j = 0; i <= r; i ++, j ++ ) a[i] = tmp[j];
}

int main()
{
    int n;
    while (~scanf("%d", &n) && n)
    {
        for (int i = 1; i <= n; i++)
        {
            scanf("%lld", &a[i]);
        }
        ans=0;
        qs(1,n);
        printf("%lld\n",ans);
    }
}

B Stars

题目大意

给出星星坐标，求出以每个星星为原点，其第三象限（含象限边界）内的星星数；

思路

由于输入是将星星按先以纵坐标升序，再以横坐标升序顺序输入的，我们可以保证对于新输入的星星，目前在场的所有星星纵坐标皆小于等于它，只需要判断横坐标小于等于它的星星有多少颗即可；

代码

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
#include <iostream>

using namespace std;
typedef long long ll;
int lowbit(int x){return x&-x;}
int c[32003],n=32001,ans[15003];

int sum(int x)
{
	int ans=0;
	for(;x;x-=lowbit(x))ans+=c[x];
	return ans;
}
void add(int x,int v)//a[p]+=v;
{
	for(;x<=n;x+=lowbit(x))c[x]+=v;
}


int main()
{
    int m,x,y;
    cin>>m;
    for(int i=1;i<=m;i++)
    {
        cin>>x>>y;
        x++,y++;
        ans[sum(x)]++;
        add(x,1);
    }
    for(int i=0;i<m;i++)
    {
        printf("%d\n",ans[i]);
    }
}

C Mobile phones

题目大意

对一个二维平面进行单点数值修改和区块数值总和查询；

思路

模拟

通过二维树状数组维护即可~

板子已经更新到帖子中；

代码

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
#include <iostream>

using namespace std;
typedef long long ll;

int c[1025][1025], n = 1024;

int lowbit(int x) { return x & -x; }

int sum(int x, int y)
{
    int ans = 0;
    for (int i = x; i > 0; i -= lowbit(i))
        for (int j = y; j > 0; j -= lowbit(j))
            ans += c[i][j];
    return ans;
}

void add(int x, int y, int v) //a[p]+=v;
{
    for (int i = x; i <= n; i += lowbit(i))
        for (int j = y; j <= n; j += lowbit(j))
            c[i][j] += v;
}

int main()
{
    int o, x, y, a, l, b, r, t;
    while (~scanf("%d", &o) && o != 3)
    {
        if (o == 1)
        {
            scanf("%d%d%d", &x, &y, &a);
            x++, y++;
            add(x,y, a);
        }
        else if (o == 2)
        {
            scanf("%d%d%d%d", &l, &b, &r, &t);
            l++, b++, r++, t++;
            int ans = sum(r,t)-sum(r,b-1)+ sum(l-1,b-1)-sum(l-1,t);
            printf("%d\n", ans);
        }
        else if (o == 0)
            scanf("%d", &a);
    }
}

D Cows

题目大意

给出每头牛对应的区间，对每头牛求出有多少个区间覆盖（至多一个端点相同）它的区间；

思路

可以先按右端点降序，左端点升序的顺序排序，若有两区间完全重合，同时保证了两区间排序后必相邻；

排序后对与每头牛，可以保证所有右端点大于其的牛都在它的左侧，如果我们统计的同时在数组中添加该头牛的左端点，则对于每头牛只需要计数目前在其左端点以左有多少个左端点即可；

注意特判重合区间；

代码

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
#include <iostream>
#include <algorithm>
#include <string.h>
using namespace std;
typedef long long ll;

int c[100005],ans[100005];
int N=100001;
pair<pair<int,int>,int>pir[100005];

int lowbit(int x) { return x & -x; }

int sum(int x)
{
	int ans=0;
	for(;x;x-=lowbit(x))ans+=c[x];
	return ans;
}

void add(int x,int v)//a[x]+=v;
{
	for(;x<=N;x+=lowbit(x))c[x]+=v;
}

bool cmp1(pair<pair<int,int>,int>a,pair<pair<int,int>,int>b)
{
    if(a.first.second==b.first.second)
    {
        return a.first.first<b.first.first;
    }
    return a.first.second>b.first.second;
}

int main()
{
    int n;
    while(~scanf("%d",&n)&&n)
    {
        memset(c,0,sizeof c);
        for(int i=1;i<=n;i++)
        {
            scanf("%d%d",&pir[i].first.first,&pir[i].first.second);
            pir[i].first.first++,pir[i].first.second++;
            pir[i].second=i;
        }
        sort(pir+1,pir+1+n,cmp1);
        //printf("*");
        for(int i=1;i<=n;i++)
        {
            if(pir[i].first==pir[i-1].first)ans[pir[i].second]=ans[pir[i-1].second];
            else
                ans[pir[i].second]=sum(pir[i].first.first);
            add(pir[i].first.first,1);
        }
        for(int i=1;i<=n;i++)
        {
            printf("%d",ans[i]);
            if(i!=n)printf(" ");
            else printf("\n");
        }
    }
}

E Get Many Persimmon Trees

题目大意

给出总区域大小，每棵树的坐标和可选区域的大小，求所有可选区域中树的最大值；

思路

不需要树状数组，用二维前缀和穷举即可；

做题的时候没意识到这一点，代码中用了树状数组；

代码

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 <iostream>
#include <algorithm>
#include <string.h>
using namespace std;
typedef long long ll;

int c[102][102], X = 100,Y=100;

int lowbit(int x) { return x & -x; }

int sum(int x, int y)
{
    int ans = 0;
    for (int i = x; i > 0; i -= lowbit(i))
        for (int j = y; j > 0; j -= lowbit(j))
            ans += c[i][j];
    return ans;
}

void add(int x, int y, int v) //a[x][y]+=v;
{
    for (int i = x; i <= X; i += lowbit(i))
        for (int j = y; j <= Y; j += lowbit(j))
            c[i][j] += v;
}

int main()
{
    int n;
    int w,h,x,y,s,t;
    while(~scanf("%d",&n)&&n)
    {
        memset(c,0,sizeof c);
        scanf("%d%d",&w,&h);
        for(int i=1;i<=n;i++)
        {
            scanf("%d%d",&x,&y);
            add(x,y,1);
        }
        scanf("%d%d",&s,&t);
        int ans=0;
        for(int i=s;i<=w;i++)
        {
            for(int j=t;j<=h;j++)
            {
                ans=max(ans,sum(i,j)-sum(i-s,j)+sum(i-s,j-t)-sum(i,j-t));
            }
        }
        printf("%d\n",ans);
    }
}

F Matrix

题目大意

二维区间修改，单点查询；

思路

可以通过树状数组维护二位前缀和实现；

实际上不需要做翻转的动作，只需要判断奇偶即可；

注意输出要求；

代码

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
#include <iostream>
#include <algorithm>
#include <string.h>
using namespace std;
typedef long long ll;

int c[1003][1003], X = 1000, Y = 1000;

int lowbit(int x) { return x & -x; }

int sum(int x, int y)
{
    int ans = 0;
    for (int i = x; i > 0; i -= lowbit(i))
        for (int j = y; j > 0; j -= lowbit(j))
            ans += c[i][j];
    return ans;
}

void add(int x, int y, int v) //a[x][y]+=v;
{
    for (int i = x; i <= X; i += lowbit(i))
        for (int j = y; j <= Y; j += lowbit(j))
            c[i][j] += v;
}

int main()
{
    int t, n, x, x1, y1, x2, y2;
    char o;
    cin >> t;
    while (t--)
    {
        scanf("%d%d", &n, &x);
        memset(c, 0, sizeof c);
        for (int i = 1; i <= x; i++)
        {
            cin>>o;
            if (o == 'C')
            {
                scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
                add(x1, y1, 1);
                add(x2 + 1, y2 + 1, 1);
                add(x1, y2 + 1, -1);
                add(x2 + 1, y1, -1);
            }
            else if (o == 'Q')
            {
                scanf("%d%d", &x1, &y1);
                printf("%d\n", sum(x1, y1) & 1);
            }
        }
        printf("\n");
    }
}

G MooFest

题目大意

给定每头牛的位置xix_i和音量viv_i，定义两牛i,ji,j交流所需要的代价为abs(xi−xj)⋅max(vi,vj)abs(x_i-x_j)\cdotp max(v_i,v_j)，求所有牛对（N(N-1)/2对）进行互相交流的总代价；

思路

我们可以按v升序排序，可以保证每头牛j 和前面交流时的max(vi,vj)=vjmax(v_i,v_j)=v_j；

接下来需要处理abs(xi−xj)abs(x_i-x_j)：
我们可以维护前面所有牛的坐标和 sumxsumx ，再通过树状数组求出前面牛中比此牛坐标小的坐标之和 ss 和头数 kk ；
那么此时的 ∑i=1i<jabs(xi−xj)=sumx−s−xj⋅(j−1−k)+xj⋅k−s\sum_{i=1}^{i<j}abs(x_i-x_j)=sumx-s-x_j\cdotp (j-1-k)+x_j\cdotp k-s；

即可求出此牛和前面所有牛交流所用代价；

代码

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
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;

pair<int,ll> c[20004];
int N=20000;
pair<int,ll>pir[20004];
int lowbit(int x) { return x & -x; }

pair<int,ll> sum(int x)
{
    pair<int,ll> ans =make_pair(0,0);
    for (int i = x; i > 0; i -= lowbit(i))
            ans.second += c[i].second,ans.first+=c[i].first;
    return ans;
}

void add(int x, pair<int,ll> v) //a[x][y]+=v;
{
    for (int i = x; i <=N; i += lowbit(i))
            c[i].first += v.first,c[i].second+=v.second;
}

int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        scanf("%d%lld",&pir[i].first,&pir[i].second);
    }
    sort(pir+1,pir+1+n);
    ll sumx=0,ans=0;
    for(int i=1;i<=n;i++)
    {
        pair<int,ll>res=sum(pir[i].second);
        ans+=pir[i].first*
            ((sumx-res.second-pir[i].second*((i-1)-res.first))+pir[i].second*res.first-res.second);
        add(pir[i].second,make_pair(1,pir[i].second));
        sumx+=pir[i].second;
    }
    printf("%lld\n",ans);
}

H Disharmony Trees

思路

和G类似~

另外地，此题需要将坐标和高度转换为顺序；

代码

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
#include <iostream>
#include <algorithm>
#include <string.h>
using namespace std;
typedef long long ll;

pair<ll,ll> c[100005];
pair<pair<ll,ll>,pair<ll,ll> > te[100005];//<x,h>
int N = 100000;

int lowbit(int x) { return x & -x; }

pair<ll,ll> sum(int x)
{
    pair<ll,ll> ans = make_pair(0,0);
    for (int i = x; i > 0; i -= lowbit(i))
            ans.second += c[i].second,ans.first+=c[i].first;
    return ans;
}

void add(int x,int v)
{
    for (int i = x; i <= N; i += lowbit(i))
            c[i].second += v,c[i].first++;
}

bool cmp(pair<pair<ll,ll>,pair<ll,ll> >a,pair<pair<ll,ll>,pair<ll,ll> >b)
{
    return a.first.second<b.first.second;
}

int main()
{
    int n;
    while(~scanf("%d",&n))
    {
        memset(c,0,sizeof c);
        for(int i=1;i<=n;i++)
        {
            scanf("%lld%lld",&te[i].first.first,&te[i].first.second);
        }
        sort(te+1,te+1+n);
        for(int i=1;i<=n;i++)
        {
            if(te[i].first.first==te[i-1].first.first)
            {
                te[i].second.first=te[i-1].second.first;
            }
            else te[i].second.first=i;
        }
        sort(te+1,te+1+n,cmp);
        for(int i=1;i<=n;i++)
        {
            if(te[i].first.second==te[i-1].first.second)
            {
                te[i].second.second=te[i-1].second.second;
            }
            else te[i].second.second=i;
        }
        ll ans=0,sumx=0;
        for(int i=n;i>=1;i--)
        {
            pair<ll,ll>tmp=sum(te[i].second.first);
            ans+=(sumx-tmp.second-te[i].second.first*(n-i-tmp.first)+tmp.first*te[i].second.first-tmp.second)*te[i].second.second;
            sumx+=te[i].second.first;
            add(te[i].second.first,te[i].second.first);
        }
        printf("%lld\n",ans);
    }
}

I KiKi’s K-Number

题目大意

对于一个容器，有三种操作：
加入数字e，删除数字e，查询大于a的第k个数；

思路

大体上可以用桶排的思路进行加入和删除维护；

对于查询，我们可以使用二分的思想快速确定；

具体看代码~

代码

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 <algorithm>
#include <string.h>
using namespace std;
typedef long long ll;

int c[100005], N = 100001;

int lowbit(int x) { return x & -x; }

int sum(int x)
{
    int ans = 0;
    for (int i = x; i > 0; i -= lowbit(i))
            ans += c[i];
    return ans;
}

void add(int x,int v) //a[x][y]+=v;
{
    for (int i = x; i <= N; i += lowbit(i))
            c[i] += v;
}

int main()
{
    int m,p,e,k;
    while (~scanf("%d",&m))
    {
        memset(c,0,sizeof c);
        while(m--)
        {
            scanf("%d%d",&p,&e);
            e++;
            if(p==0)
            {
                add(e,1);
            }
            else if(p==1)
            {
                if(sum(e)-sum(e-1))
                {
                    add(e,-1);
                }
                else printf("No Elment!\n");
            }
            else
            {
                scanf("%d",&k);
                int l=e,r=N+1;
                while(l<r)
                {
                    int mid=l+r>>1;
                    if(sum(mid)-sum(e)>=k)r=mid;
                    else l=mid+1;
                }
                if(l==N+1)
                printf("Not Find!\n");
                else 
                printf("%d\n",l-1);
            }
        }
    }
}

J Reverse Prime

题目大意

定义了“反向指数”，要求进行两种操作：
删除反向质数e，查询前 i 个反向质数的质因数数量之和；

思路

具体查询过程和 I 题类似；

对于一个被删除的的反向质数，我们可以标记删除，并在维护质因数数量的树状数组中的那一位清零（删除等量的质因数）；
对于查询操作，使用二分思想，找到该位之前满足剩余 i 个的位置；

代码

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
#include <iostream>
#include <algorithm>
#include <string.h>
#include <math.h>
#include <map>
using namespace std;
typedef long long ll;

int c[80004],N = 78500 , del[80004];

int lowbit(int x) { return x & -x; }

ll sum(int* c,int x)
{
    ll ans =0;
    for (int i = x; i > 0; i -= lowbit(i))
            ans += c[i];
    return ans;
}

void add(int *c,int x,int v)
{
    for (int i = x; i <= N; i += lowbit(i))
            c[i]+= v;
}

int n[1000006],p[80004],ct[80004],rp[80004];
map<int,int>mp;
int main()
{
    int cp=0;
    for(int i=2;i<1000000;i++)
    {
        if(!n[i])p[cp++]=i;
        for(int j=0;j<cp&&p[j]*i<1000000;j++)
        {
            n[p[j]*i]=1;
            if(i%p[j]==0)break;
        }
    }
    for(int i=0;i<cp;i++)
    {
        ll as=0,tmp=p[i];
        for(tmp;tmp;tmp/=10)
        {
            as*=10,as+=tmp%10;
        }
        while(as<1000000)as*=10;
        rp[i+1]=as;
    }
    sort(rp+1,rp+cp+1);
    for(int i=1;i<=cp;i++)
    {
        ll as=rp[i];
        //printf("%d\n",as);
        mp[as]=i;
        for(int j=0;p[j]<=sqrt(as)&&j<cp;j++)
        {
            while(as%p[j]==0)
            {
                as/=p[j];
                ct[i]++;
            }
        }
        if(as>1)ct[i]++;
        add(c,i,ct[i]);
    }
    //printf("%d",ct[1]);
    char o;
    int x;
    while(cin>>o)
    {
        scanf("%d",&x);
        if(o=='d')
        {
            int i=mp[x];
            mp[x]=0;
            if(!i)continue;
            add(del,i,1);
            add(c,i,-ct[i]);
        }
        else
        {
            x++;
            if(x>78498)x=78498;
            int l=x,r=78499;
            while(l<r)
            {
                int mid=l+r>>1;
                if(mid-sum(del,mid)>=x)r=mid;
                else l=mid+1;
            }
            printf("%lld\n",sum(c,l));
        }
    }
}

ED

\

算法竞赛 > 比赛与题集
NEFU大一暑假集训-树状数组
https://tanyuu.github.io/2021.07-12/NEFU大一暑假集训-树状数组/
作者
F Juny
发布于
2021年8月19日
许可协议