MYF

HDU 5057 Argestes and Sequence

Posted on | In | | Visitors

题目链接

HDU 5057

解题方法：离线统计 + 树状数组

题目分析

题目大意

给出n个数字和m个操作，操作分为查询Q和更改S，当查询时给出l, r, d, p表示下标在查询[l, r]区间内从低到高第d位为p的值的数量，当更改时给出X Y表示将第X个数的值修改为Y，求出所有查询的结果。

解析

区间查询，很容易想到线段数和树状数组，但是从数据量来看，要枚举每一个数字的每一位，相当于需要三维数组（数字下标、每个数字的位下标、值），需要的空间太大，所以采取时间换空间的方式，我们枚举每个数字的位下标信息，这样只需要开二维数组（数的下标和值）即可解决问题。树状数组原本只需要一维数组即可解决问题，但是有十个值（0~9），所以在树状数组的更新函数以及求和函数需要加上值信息，相当于十个一维树状数组，查询时每次求区间的和即可。

参考链接：HDU 5057 Argestes and Sequence（树状数组+离线 OR 分块）——SIO_Five

代码

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
#include <set>
#include <map>
#include <stack>
#include <cmath>
#include <queue>
#include <cstdio>
#include <string>
#include <vector>
#include <iomanip>
#include <cstring>
#include <iostream>
#include <deque>
#include <algorithm>
#define Memset(a,val) memset(a,val,sizeof(a))
#define PI acos(-1)
#define rt(n)       (i == n ? '\n' : ' ')
#define hi         printf("Hi----------\n")
#define IN freopen("input.txt","r",stdin);
#define OUT freopen("output.txt","w",stdout);
#define debug(x) cout<<"Debug : ---"<<x<<"---"<<endl;
#pragma comment(linker, "/STACK:1024000000,1024000000")
typedef long long ll;
using namespace std;
const int maxn=100000+5;
const int mod=1000000007;
const int INF=0x3f3f3f3f;
const double eps=1e-8;
int a[100005];  //用于记录初始的n个值
int b[100005];  //用于记录各数的第i位
int c[100005][15];  //用于记录树状数组
int n , m ;
struct Operation{
    int l, r, d ,p, id, x, y, ans;
}op[100005];
int lowbit(int x){
    return x&(-x);
}
void update(int idx,int pos,int val){
    while (idx<=n) {
        c[idx][pos]+=val;
        idx+=lowbit(idx);
    }
}
int sum(int idx,int pos){
    int ans=0;
    while (idx>0) {
        ans+=c[idx][pos];
        idx-=lowbit(idx);
    }
    return ans;
}
int main(){
    char s[10];
    int t;
    scanf("%d",&t);
    while (t--) {
        scanf("%d%d",&n,&m);
        for (int i=1; i<=n; i++) {
            scanf("%d",&a[i]);
        }
        for (int i=1; i<=m; i++) {
            scanf("%s",s);
            if (s[0]=='Q') {
                scanf("%d %d %d %d",&op[i].l,&op[i].r,&op[i].d,&op[i].p);
                op[i].id=1;
            }
            else{
                scanf("%d %d",&op[i].x,&op[i].y);
                op[i].id=0;
            }
        }
        
        
        // 枚举十位——int范围只有10位
        for (int i=1,base=1; i<=10; i++,base*=10) {
            Memset(c, 0);
            //将初始情况记录到树状数组中
            for (int j=1; j<=n; j++) {
                b[j]=a[j]/base%10;
                update(j,b[j],1);
            }
            
            for (int j=1; j<=m; j++) {
                if (op[j].id==0) {
                    update(op[j].x,b[op[j].x], -1); //删除原数字的信息
                    b[op[j].x]=op[j].y/base%10;
                    update(op[j].x,b[op[j].x], 1);
                }
                else if(op[j].d==i){
                    op[j].ans=sum(op[j].r,op[j].p)-sum(op[j].l-1,op[j].p);  //求区间的和
                }
            }
        }
        
        for (int j=1; j<=m; j++) {
            if (op[j].id) {
                cout<<op[j].ans<<endl;
            }
        }
    }
    return 0;
}