离散化
离散化
应用场景
当数的范围非常大，而用到的数又十分稀疏的时候，使用离散化的方法来处理。
题目
模板题： acwing 802 区间和（vector实现去重和离散化）
假定有一个无限长的数轴，数轴上每个坐标上的数都是0。
现在，我们首先进行 n 次操作，每次操作将某一位置x上的数加c。
接下来，进行 m 次询问，每个询问包含两个整数l和r，你需要求出在区间[l, r]之间的所有数的和。
输入格式
第一行包含两个整数n和m。
接下来 n 行，每行包含两个整数x和c。
再接下里 m 行，每行包含两个整数l和r。
输出格式
共m行，每行输出一个询问中所求的区间内数字和。
数据范围
$ 10 ^ 9 $ ≤ x ≤ $ 10 ^ 9 $
1≤n,m≤$ 10 ^ 5 $
−$10^9$≤l≤r≤$10^9$
−10000≤c≤10000
输入样例：
1
2
3
4
5
6
7
| 3 3
1 2
3 6
7 5
1 3
4 6
7 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
59
60
61
62
63
64
| #include<iostream>
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
const int N=300050;
int n,m;
int a[N],sum[N];
typedef pair<int,int> pii;
vector <int> s;
vector <pii> add,q;
int find(int x)
{
int l=0,r=s.size()-1;
while(l<r)
{
int mid=(l+r)>>1;
if(s[mid]>=x)r=mid;
else l=mid+1;
}
return r+1;
}
int main()
{
ios::sync_with_stdio(false);
cin>>n>>m;
for(int i=1;i<=n;i++)
{
int x,c;
cin>>x>>c;
add.push_back({x,c});
s.push_back(x);
}
for(int i=1;i<=m;i++)
{
int l,r;
cin>>l>>r;
q.push_back({l,r});
s.push_back(l);
s.push_back(r);
}
sort(s.begin(),s.end());
s.erase(unique(s.begin(),s.end()),s.end());
for(auto item:add)
{
int x=find(item.first);
a[x]+=item.second;
}
for(int i=1;i<=s.size();i++)
{
sum[i]=sum[i-1]+a[i];
}
for(auto item:q)
{
int l=find(item.first),r=find(item.second);
cout<<sum[r]-sum[l-1]<<endl;
}
return 0;
}
|
洛谷 P1908逆序对【树状数组做法】
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
| #include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std;
const int N=500050;
ll tree[N],b[N];
int n;
ll ans=0;
struct node
{
ll val,num;
}a[N];
ll lowbit(ll k)
{
return k&(-k);
}
void add(ll k)
{
while(k<=n)
{
tree[k]+=1;
k+=lowbit(k);
}
}
ll getsum(ll k)
{
ll sum=0;
while(k)
{
sum+=tree[k];
k-=lowbit(k);
}
return sum;
}
bool cmp(node x,node y)
{
if(x.val==y.val) return x.num<y.num;
return x.val<y.val;
}
int main()
{
ios::sync_with_stdio(false);
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i].val;
a[i].num=i;
}
sort(a+1,a+n+1,cmp);
for(int i=1;i<=n;i++)
{
b[a[i].num]=i;
}
for(int i=n;i>=1;i--)
{
add(b[i]);
ans+=getsum(b[i]-1);
}
cout<<ans;
return 0;
}
|
CSDN离散化