首页 > 代码库 > hdu3333-Turing Tree-线段树+离线+离散化
hdu3333-Turing Tree-线段树+离线+离散化
前言：引用某某的话——我是猪QAQ。。。。。
题意就不复述了。
解题思路：
一般的建树，求和。
离散化：用另一个数组sor[]记录原数组，sort一遍，用unique去重，用sor[]数组元素下标，代替原数组中元素，然后在sor[]数组里二分查找元素，last[]数组记录第i个元素上一次出现的位置。
离线处理：将查询按右边界从小到大排序，依次处理区间[1, r1]、[r1+1, r2]、[r2+1, r3]......将重复的元素的前一个（记录在last里）在线段树里单点更新删去, 然后将query（li, ri）的值记录到相应的位置。同时，在读入时记录是第几个查询用于后面输出。
复杂度：O（nlogn）
AC代码：
1 #include <iostream> 2 #include <cstdio> 3 #include <vector> 4 #include <cstring> 5 #include <algorithm> 6 using namespace std; 7 #define lson l, m, rt<<1 8 #define rson m+1, r, rt<<1|1 9 int n, m; 10 struct node 11 { 12 int l, r; 13 int num; 14 bool operator < (const node that) const{ 15 return r < that.r; 16 } 17 }; 18 bool uni(int i, int j) 19 { 20 return i == j; 21 } 22 vector<node> brr; 23 vector<int> sor; 24 vector<int> arr; 25 long long sgt[1200080]; 26 int last[30005]; 27 long long ans[300005]; 28 void input() 29 { 30 brr.clear(); sor.clear(); arr.clear(); 31 memset(last, -1, sizeof(last)); 32 scanf("%d", &n); 33 for(int i = 0; i < n; i++) { 34 int a; scanf("%d", &a); 35 arr.push_back(a); 36 sor.push_back(a); 37 } 38 sort(sor.begin(), sor.end()); 39 vector<int>::iterator it; 40 it = unique(sor.begin(), sor.end(), uni); 41 sor.resize(distance(sor.begin(), it)); //离散化 42 scanf("%d", &m); 43 for(int i = 0; i < m; i++) { 44 node x; scanf("%d%d", &x.l, &x.r); 45 x.num = i; //记录询问的顺序 46 brr.push_back(x); 47 } 48 sort(brr.begin(), brr.end()); 49 } 50 void push_up(int rt) 51 { 52 sgt[rt] = sgt[rt<<1] + sgt[rt<<1|1]; 53 } 54 void build(int l, int r, int rt) 55 { 56 if(l == r) { 57 sgt[rt] = arr[l-1]; 58 return; 59 } 60 int m = (l + r)>>1; 61 build(lson); 62 build(rson); 63 push_up(rt); 64 } 65 void Delete(int l, int r, int rt, int pos) 66 { 67 if(l == r) { 68 sgt[rt] = 0; return ; 69 } 70 int m = (l+r)>>1; 71 if(pos <= m) Delete(lson, pos); 72 else Delete(rson, pos); 73 push_up(rt); 74 } 75 long long query(int l, int r, int rt, int L, int R) 76 { 77 if(L <= l && r <= R) { 78 return sgt[rt]; 79 } 80 long long res = 0; 81 int m = (l+r)>>1; 82 if(L <= m) res += query(lson, L, R); 83 if(m < R) res += query(rson, L, R); 84 return res; 85 } 86 87 void work() 88 { 89 build(1, n, 1); 90 int l, r; 91 for(int i = 0; i < m; i++) { 92 r = brr[i].r-1; 93 if(i == 0) l = 0; 94 else l = brr[i-1].r; 95 for(int j = l; j <= r; j++) { 96 int pos = lower_bound(sor.begin(), sor.end(), arr[j]) - sor.begin(); //pos对应离散化后的元素下标 97 if(last[pos] == -1) { //前面无重复 98 last[pos] = j; continue; 99 }100 Delete(1, n, 1, last[pos]+1); last[pos] = j; //删除重复元素，更改last为元素当前位置。101 }102 ans[brr[i].num] = query(1, n, 1, brr[i].l, brr[i].r); //将结果填在询问的顺序位置103 }104 for(int i = 0; i < m; i++) {105 printf("%I64d\n", ans[i]);106 }107 }108 int main()109 {110 int t; cin>>t;111 while(t--) {112 input();113 work();114 }115 return 0;116 }
hdu3333-Turing Tree-线段树+离线+离散化
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。