Super Mario
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 5560 Accepted Submission(s): 2532
For each test data:
The first line contains two integers n, m (1 <= n <=10^5, 1 <= m <= 10^5), n is the length of the road, m is the number of queries.
Next line contains n integers, the height of each brick, the range is [0, 1000000000].
Next m lines, each line contains three integers L, R,H.( 0 <= L <= R < n 0 <= H <= 1000000000.)
10 10
0 5 2 7 5 4 3 8 7 7
2 8 6
3 5 0
1 3 1
1 9 4
0 1 0
3 5 5
5 5 1
4 6 3
1 5 7
5 7 3
4
0
0
3
1
2
0
1
5
1
http://acm.hdu.edu.cn/showproblem.php?pid=4417
一开始的时候,很难想,和以前的树状数组不同,但是有一点是固定的。
既然要是区间里的个数,那么就肯定离不开L, R
开始的时候还以为学以前的区间统计不同数字的个数一样。对R排序,然后每个压进树状数组。
但是这样不行,查询元素的变得十分麻烦。
比如1、5、7、3
我把这些元素都压进去了,然后查询[3, 4]小于等于6的个数,就会很麻烦。
既要减去[1, 2]的,也有些数字比6大。、
主要是没用上L和R。这两个是必须用的,都是getsum(R) - getsum(L - 1)进而得到答案。都是这个套路。
那么就是看看[L, R]这一段连续的区间,有多少个数是小于等于val的。那么我们先保证,现在每一个压进树状
数组的元素都是<=val的,这个可以保证,然后更新数字的时候,就是跟新他们的位置,所以这时候查询就直接来就行了。
这一招保证每一次query的时候元素都是合法的技巧,以前用过一次,可惜忘记了。
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <assert.h>
#define IOS ios::sync_with_stdio(false)
using namespace std;
#define inf (0x3f3f3f3f)
typedef long long int LL; #include <iostream>
#include <sstream>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <string>
const int maxn = 1e5 + ;
int c[maxn];
int n, m;
int lowbit(int x) {
return x & (-x);
}
void UpDate(int pos, int val) {
while (pos <= n) {
c[pos] += val;
pos += lowbit(pos);
}
}
int getsum(int pos) {
int ans = ;
assert(pos >= );
while (pos) {
ans += c[pos];
pos -= lowbit(pos);
}
return ans;
}
struct haha {
int val, id;
bool operator < (const struct haha & rhs) const {
return val < rhs.val;
}
}a[maxn];
struct node {
int L, R, id, val;
bool operator < (const struct node & rhs) const {
return val < rhs.val;
}
}query[maxn];
int ans[maxn];
void init() {
memset(c, , sizeof c);
}
void work() {
scanf("%d%d", &n, &m);
for (int i = ; i <= n; ++i) {
scanf("%d", &a[i].val);
a[i].id = i;
}
sort(a + , a + + n);
for (int i = ; i <= m; ++i) {
scanf("%d%d%d", &query[i].L, &query[i].R, &query[i].val);
query[i].L++;
query[i].R++;
query[i].id = i;
}
sort(query + , query + + m);
int now = ;
for (int i = ; i <= m; ++i) {
while (now <= n && query[i].val >= a[now].val) {
UpDate(a[now].id, );
now++;
}
ans[query[i].id] = getsum(query[i].R) - getsum(query[i].L - );
}
static int f = ;
printf("Case %d:\n", ++f);
for (int i = ; i <= m; ++i) {
printf("%d\n", ans[i]);
}
} int main() {
#ifdef local
freopen("data.txt", "r", stdin);
// freopen("data.txt", "w", stdout);
#endif
int t;
scanf("%d", &t);
while (t--) {
init();
work();
}
return ;
}
我这个线段树不是其他线段树。
我的每个节点都保存了所有区间的数字。并且排序
就是把归并排序的过程记录下来了。
然后对于每一个个查询。
1、如果区间全部包含了,那么直接二分查找即可。
2、递归搜索。
注意pushUp的时候,要先vector<>.resize();
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <assert.h>
#define IOS ios::sync_with_stdio(false)
using namespace std;
#define inf (0x3f3f3f3f)
typedef long long int LL; #include <iostream>
#include <sstream>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <string>
#define root 1, n, 1
#define lson L, mid, cur << 1
#define rson mid + 1, R, cur << 1 | 1
const int maxn = 1e5 + ;
vector<int>seg[maxn << ];
int a[maxn];
int n, m;
void pushUp(int cur) {
// cout << "ff" << endl;
// cout << seg[cur << 1].size() << endl;
merge(seg[cur << ].begin(), seg[cur << ].end(), seg[cur << | ].begin(), seg[cur << | ].end(), seg[cur].begin());
}
void build(int L, int R, int cur) {
if (L == R) {
seg[cur].clear();
seg[cur].push_back(a[L]);
return;
}
int mid = (L + R) >> ;
build(lson);
build(rson);
seg[cur].resize(R - L + );
pushUp(cur);
}
int query(int be, int en, int val, int L, int R, int cur) {
if (L >= be && R <= en) {
if (val >= seg[cur].back()) {
return R - L + ;
} else {
int pos = upper_bound(seg[cur].begin(), seg[cur].end(), val) - seg[cur].begin();
return pos;
}
}
int mid = (L + R) >> ;
int lans = , rans = ;
if (mid >= be) {
lans = query(be, en, val, lson);
}
if (mid < en) {
rans = query(be, en, val, rson);
}
return lans + rans;
}
void upDate(int pos, int val, int L, int R, int cur) {
if (L == R) {
if (pos == L) {
seg[cur].clear();
seg[cur].push_back(val);
}
return;
}
int mid = (L + R) >> ;
if (pos <= mid) upDate(pos, val, lson);
else upDate(pos, val, rson);
pushUp(cur);
}
void work() {
scanf("%d%d", &n, &m);
// cout << n << " " << m << endl;
for (int i = ; i <= n; ++i) {
scanf("%d", &a[i]);
}
build(root);
// for (int i = 0; i < seg[1].size(); ++i) {
// cout << seg[1][i] << " ";
// }
// cout << endl;
// cout << "ff" << endl;
static int f = ;
printf("Case %d:\n", ++f);
while (m--) {
int be, en, x;
scanf("%d%d%d", &be, &en, &x);
be++;
en++;
int res = query(be, en, x, root);
printf("%d\n", res);
}
} int main() {
#ifdef local
freopen("data.txt", "r", stdin);
// freopen("data.txt", "w", stdout);
#endif
int t;
scanf("%d", &t);
while (t--) work();
return ;
}