2015
07-16

# Super Mario

Mario is world-famous plumber. His “burly” figure and amazing jumping ability reminded in our memory. Now the poor princess is in trouble again and Mario needs to save his lover. We regard the road to the boss’s castle as a line (the length is n), on every integer point i there is a brick on height hi. Now the question is how many bricks in [L, R] Mario can hit if the maximal height he can jump is H.

The first line follows an integer T, the number of test data.
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.)

The first line follows an integer T, the number of test data.
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.)

1
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

Case 1:
4
0
0
3
1
2
0
1
5
1

#include <iostream>
#include <cstdio>
#include <string.h>
#include <algorithm>
using namespace std;

const int N = 100010;
struct dit{
int num,id;
}dd[N];
int lp,rp,value,id;
}aa[N];
int cnt[N];
bool cmp1(dit a,dit b){
return a.num < b.num;
}
return a.value < b.value;
}
int inline lowbit(int x){
return x & (-x);
}
void inline update(int x){
while(x < N){
cnt[x]++;
x += lowbit(x);
}
}
int inline sum(int x){
int s = 0;
while(x > 0){
s += cnt[x];
x -= lowbit(x);
}
return s;
}
int main(){
//freopen("1.txt","r",stdin);
int numcase;
scanf("%d",&numcase);
for(int ca = 1; ca <= numcase; ++ca){
int n,m;
memset(cnt,0,sizeof(cnt));
scanf("%d%d",&n,&m);
for(int i = 0; i < n; ++i){
scanf("%d",&dd[i].num);
dd[i].id = i + 1;
}
int x,y;
for(int i = 0; i < m; ++i){
scanf("%d%d%d",&x,&y,&aa[i].value);
aa[i].lp = x + 1;
aa[i].rp = y + 1;
aa[i].id = i + 1;
}
sort(dd,dd+n,cmp1);
sort(aa,aa+m,cmp2);
int ans[N] = {0};
for(int aski = 0,ditj = 0; aski < m; ++aski){
while(ditj < n && aa[aski].value >= dd[ditj].num){
update(dd[ditj].id);
ditj++;
}
}
printf("Case %d:\n",ca);
for(int i = 1; i <= m; ++i){
printf("%d\n",ans[i]);
}
}
return 0;
}

1. 你的说法根本算不上思维，只是简单跟风。任何一个伟大的存在的古文明只要有成就。而这些成就就是大脑思维的进化，科技文化，都是同步进行除非像现在给你洗脑，我们的党国怎么样？金钱权力的白骨就是而看到国外的不流行的国家也有喜怒悲哀和有趣的思维和文化还有发明我们就稀