HDU 4417 Super Mario (树状数组+离线处置)
HDU 4417 Super Mario (树状数组+离线处理)
题意: 给定1--n区间,有q个询问,询问l,r,k表示区间[l,r]小于等于k的数的个数
思路: 可以用划分树(求区间第k大值)变形一下,来求小于等于k的个数,但是此题直接离线处理询问高效的多。
首先将1--n区间的值记录位置,从小到大排序,每个询问按照k值从小到大排序,然后从小到大开始,根据查询的H,将满足条件的的点插入,计数+1,然后就是求区间和。
#include <iostream> #include <algorithm> #include <cmath> #include<functional> #include <cstdio> #include <cstdlib> #include <cstring> #include <string> #include <vector> #include <set> #include <queue> #include <stack> #include <climits>//形如INT_MAX一类的 #define MAX 100001 using namespace std; inline void RD(int &ret) { char c; do { c = getchar(); } while(c < '0' || c > '9') ; ret = c - '0'; while((c=getchar()) >= '0' && c <= '9') ret = ret * 10 + ( c - '0' ); } void OT(int a) { if(a >= 10)OT(a / 10); putchar(a % 10 + '0'); } int n,q; struct node { int v,id; } a[MAX]; int c[MAX]; struct QES { int l,r,h,id; } qes[MAX]; int ans[MAX]; bool cmp(const node &a, const node &b) { return a.v < b.v; } bool cmp2(const QES &a, const QES &b) { return a.h < b.h; } int lowbit(int x) { return x & (-x); } void update(int x,int va) { while(x <= n) { c[x] += va; x += lowbit(x); } } int query(int x) { int ans = 0; while(x > 0) { ans += c[x]; x -= lowbit(x); } return ans; } int main() { int T; cin >> T; int ca = 1; while(T--) { RD(n); RD(q); memset(c,0,sizeof(c)); for(int i=1; i<=n; i++) { RD(a[i].v); a[i].id = i; } sort(a+1,a+1+n,cmp); for(int i=0; i<q; i++) RD(qes[i].l),RD(qes[i].r),RD(qes[i].h),qes[i].id = i; sort(qes,qes+q,cmp2); int order = 1; for(int i=0; i<q; i++) { while(a[order].v <= qes[i].h && order <= n) { update(a[order].id,1); order ++; } ans[qes[i].id] = query(qes[i].r+1) - query(qes[i].l); } printf("Case %d:\n",ca++); for(int i=0; i<q; i++)OT(ans[i]),puts(""); } return 0; }