hdu-3333 Turing Tree 离线区间+树状数组（区间不同数的和）
标签：strong lowbit \n 一个 class define bool 元素 引用
题目链接：
http://acm.hdu.edu.cn/showproblem.php?pid=3333
题目大意：
给出一数组，以及m个查询区间，每次查询该区间不同数字的和。相同数字只加一次。
解题思路：
离线区间，按照区间右端点进行排序。
这样可以从左到右扫一遍，用尺取法一个一个将数字放入树状数组中。
如果这个数字已经在树状数组里面，记录之前的下标，再从树状数组中删去之前下标的这个数字，在当前下标添加该数字。这样可以保证每一步操作，都会使得树状数组中没有重复元素。这样可以直接用树状数组求不同数字的和。
求区间种类数也是这样做。
1 #include 2 #define IOS ios::sync_with_stdio(false);//不可再使用scanf printf
3 #define Max(a, b) ((a) > (b) ? (a) : (b))
4 #define Min(a, b) ((a) 5 #define Mem(a) memset(a, 0, sizeof(a))
6 #define Dis(x, y, x1, y1) ((x - x1) * (x - x1) + (y - y1) * (y - y1))
7 #pragma comment(linker, "/STACK:102400000,102400000")//栈外挂
8 using namespace std;
9 inline int read()
10 {
11 int x=0,f=1;char ch=getchar();
12 while (ch‘0‘||ch>‘9‘){if (ch==‘-‘) f=-1;ch=getchar();}
13 while (ch>=‘0‘&&ch‘9‘){x=x*10+ch-‘0‘;ch=getchar();}
14 return x*f;
15 }
16
17 typedef long long ll;
18 const int maxn = 100000 + 10;
19 const int MOD = 1000000007;//const引用更快，宏定义也更快
20 ll a[maxn];//树状数组
21 ll c[maxn];//原数组
22 mapint>Last;//记录上一次出现该值的下标
23 int n;
24 int lowbit(int x)
25 {
26 return x & (-x);
27 }
28 //向后修改某一点的值
29 void add(int x, ll d)
30 {
31 //cout
32 while(x n)
33 {
34 a[x] += d;
35 x += lowbit(x);
36 }
37 }
38 //向前统计[1, x]的区间和
39 ll sum(int x)
40 {
41 ll ret = 0;
42 while(x > 0)
43 {
44 ret += a[x];
45 x -= lowbit(x);
46 }
47 return ret;
48 }
49 struct node
50 {
51 int l, r;
52 int id;
53 node(){}
54 bool operator const node& a)const
55 {
56 return r a.r;
57 }
58 }cnt[maxn];//离线区间
59 ll ans[maxn];
60 int main()
61 {
62 int T, cases = 0;
63 scanf("%d", &T);
64 while(T--)
65 {
66 Last.clear();
67 Mem(a);
68 int m;
69 scanf("%d", &n);
70 for(int i = 1; i "%lld", &c[i]);
71 scanf("%d", &m);
72 for(int i = 1; i "%d%d", &cnt[i].l, &cnt[i].r), cnt[i].id = i;
73 sort(cnt + 1, cnt + 1 + m);
74 int pre = 1;
75 for(int i = 1; i )
76 {
77 for(int j = pre; j )
78 {
79 if(Last[c[j]])//之前出现过
80 {
81 add(Last[c[j]], -c[j]);
82 }
83 add(j, c[j]);
84 Last[c[j]] = j;
85 }
86 pre = cnt[i].r + 1;
87 ans[cnt[i].id] = sum(cnt[i].r) - sum(cnt[i].l - 1);
88 }
89 for(int i = 1; i "%lld\n", ans[i]);
90 }
91 return 0;
92 }
hdu-3333 Turing Tree 离线区间+树状数组（区间不同数的和）
标签：strong lowbit \n 一个 class define bool 元素 引用
原文地址：https://www.cnblogs.com/fzl194/p/9565885.html
评论