题目链接:hdu 3333 Turing Tree
题目大意:给定一个长度为N的序列,有M次查询,每次查询l,r之间元素的总和,相同元素只算一次。
解题思路:涨姿势了,线段树的一种题型,离线操作,将查询按照右区间排序,每次考虑一个询问,将mv ~ r的点全部标记为存在,并且对于每个位置i,如果A[i]在前面已经出现过了,那么将前面的那个位置减掉A[i],当前位置添加A[i],这样做维护了每个数尽量做,那么碰到查询,用sum[r] - sum[l-1]即可。
#include <cstdio>
#include <cstring>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;
typedef long long ll;
const int maxn = 30000;
int N, Q;
ll A[maxn+5], ans[100005];
map<ll, int> G;
#define lson(x) ((x)<<1)
#define rson(x) (((x)<<1)|1)
int lc[maxn << 2], rc[maxn << 2];
ll s[maxn << 2];
inline void pushup (int u) {
s[u] = s[lson(u)] + s[rson(u)];
}
void build (int u, int l, int r) {
lc[u] = l;
rc[u] = r;
s[u] = 0;
if (l == r)
return;
int mid = (lc[u] + rc[u]) / 2;
build(lson(u), l, mid);
build(rson(u), mid + 1, r);
pushup(u);
}
void modify(int u, int x, ll d) {
if (x == lc[u] && rc[u] == x) {
s[u] += d;
return;
}
int mid = (lc[u] + rc[u]) / 2;
if (x <= mid)
modify(lson(u), x, d);
else
modify(rson(u), x, d);
pushup(u);
}
ll query(int u, int l, int r) {
if (l <= lc[u] && rc[u] <= r)
return s[u];
ll ret = 0;
int mid = (lc[u] + rc[u]) / 2;
if (l <= mid)
ret += query(lson(u), l, r);
if (r > mid)
ret += query(rson(u), l, r);
pushup(u);
return ret;
}
struct Seg {
int l, r, id;
Seg (int l = 0, int r = 0, int id = 0) {
this->l = l;
this->r = r;
this->id = id;
}
friend bool operator < (const Seg& a, const Seg& b) {
return a.r < b.r;
}
};
vector<Seg> vec;
void init () {
int l, r;
G.clear();
vec.clear();
scanf("%d", &N);
for (int i = 1; i <= N; i++)
scanf("%I64d", &A[i]);
scanf("%d", &Q);
for (int i = 1; i <= Q; i++) {
scanf("%d%d", &l, &r);
vec.push_back(Seg(l, r, i));
}
sort(vec.begin(), vec.end());
}
void solve () {
build (1, 0, N);
int k = 0;
for (int i = 0; i < Q; i++) {
for ( ; k <= vec[i].r; k++) {
if (G[A[k]])
modify(1, G[A[k]], -A[k]);
G[A[k]] = k;
modify(1, k, A[k]);
}
ans[vec[i].id] = query(1, vec[i].l, vec[i].r);
}
for (int i = 1; i <= Q; i++)
printf("%I64d\n", ans[i]);
}
int main () {
int cas;
scanf("%d", &cas);
while (cas--) {
init();
solve();
}
return 0;
}
分享到:
相关推荐
Hdu 3333解题报告 题意描述: 给你n个数现在要你求在k个区间上[ai, bi]的不相同的数之和各是多少. N,000; k,000; 显然,这题不能用暴力来做。 这题我们选择用线段数来做。
hdu 1166线段树代码
hdu 1166线段树
从简单入门到偏中等的几个题,线段树很灵活,主要懂了lazy操作,其他的自己yy吧。
【hdu5306】Gorgeous Sequence 线段树区间最值操作-附件资源
线段树入门资料,有利于初学者学习,让他们详细了解线段树。
NULL 博文链接:https://128kj.iteye.com/blog/1738772
大量线段树题目 zoj 1610 线段覆盖 poj 2777 线段覆盖 poj 2528 需要离散化,建树不同,需要处理不同->注意这组数据 3 1 10 1 3 6 10 the ans is 3. hdu 1754 求区间最大值 hdu 1166 求区间和 hdu 1698 成段更新 ...
300+ AC 代码 。 大数 , 线段树 , 字符串 , dp.....
HDU的1250,主要是利用高精度加法,但是代码有点繁琐,效率不是很高
题面 【题目描述】 有nnn个营地,已知每个营地的人数,有四条命令: (1)Add(1) Add(1)Add iii jjj,iii和jjj为正整数,表示第iii个营地增加jjj个人(jjj不超过303030) (2)Sub(2)Sub(2)Sub iii jjj ,iii和jjj为正...
HDU1059的代码
杭电ACMhdu1163
hdu1001解题报告
hdu 1574 passed sorce
HDU的一题........HDU DP动态规
hdu acm 教案 搜索入门 hdu acm 教案 搜索入门
hdu2101AC代码
搜索 dfs 解题代码 hdu1241