HDU---4417Super Mario 树状数组离线操作

浏览数：39 / 时间：2015年06月08日

题意：给定 n个数，查询位置L R内小于x的数有多少个。

对于某一次查询把所有比x小的数 ”的位置“ 都加入到树状数组中，然后sum(R)-sum(L-1)就是答案，q次查询就要离线操作了，按高度排序。

#include <set>
#include <map>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <cctype>
#include <cstdio>
#include <string>
#include <vector>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
const int inf = 0x3f3f3f3f;
const double eps = 1e-8;
template <class T>
inline bool scan_d(T &ret)
{
    char c;
    int sgn;
    if(c=getchar(),c==EOF)
    return 0;
    while(c!=‘-‘&&(c<‘0‘||c>‘9‘))     c=getchar();
    sgn = (c==‘-‘)?-1:1;
    ret =(c==‘-‘)?0:(c-‘0‘);
    while(c=getchar(),c>=‘0‘&&c<=‘9‘)     ret=ret*10+(c-‘0‘);
    ret*=sgn;
    return 1;
}
const int maxn = 1e5+100;
int n,q,c[maxn];
int lowbit (int x)
{
    return x & -x;
}
void add(int x,int d)
{
    while (x <= n)
    {
        c[x] += d;
        x += lowbit(x);
    }
}
int sum(int x)
{
    int ans = 0;
    while (x > 0)
    {
        ans += c[x];
        x -= lowbit(x);
    }
    return ans;
}
struct Node1
{
    int v,index;
}h[maxn];
struct Node2
{
    int l,r,v,index,ans;
}H[maxn];
bool cmp1(const Node1 &n1,const Node1 &n2)
{
    return n1.v < n2.v;
}
bool cmp2(const Node2 &n1,const Node2 &n2)
{
    return n1.v < n2.v;
}
bool cmp3(const Node2 &n1,const Node2 &n2)
{
    return n1.index < n2.index;
}
int main(void)
{
    #ifndef ONLINE_JUDGE
        freopen("in.txt","r",stdin);
    #endif
    int t,cas = 1;
     scanf ("%d",&t);
    while (t--)
    {
        memset(c,0,sizeof(c));
        scanf ("%d%d",&n,&q);
        for (int i = 1; i <= n; i++)
        {
            scanf ("%d",&h[i].v);
            h[i].index = i;
        }
        sort(h+1,h+n+1,cmp1);
        for (int i = 1; i <= q; i++)
        {
            scanf ("%d%d%d",&H[i].l,&H[i].r,&H[i].v);
            H[i].l++;
            H[i].r++;
            H[i].index = i;
        }
        sort(H+1,H+q+1,cmp2);
        int j = 1;
        for (int i = 1; i <= q; i++)
        {
            int tmp = H[i].v;
            while (h[j].v <= tmp&&j<=n)      //这里要加j<=n 不然会死循环
            {
                add(h[j].index,1);
                j++;
            }
            H[i].ans = sum(H[i].r) - sum(H[i].l-1);
        }
        sort(H+1,H+q+1,cmp3);
        printf("Case %d:\n",cas++);
        for (int i = 1; i <= q; i++)
        {
            printf("%d\n",H[i].ans);
        }
    }
    return 0;
}