学步园

离线线段树，和上次做的BC是一样样的题。

题目大意，给你一串n项有序数列，然后再给m次查询，要找到查询区间内满足小于所查询的值的数的个数。然后是非常典型的离线线段树题。把所有的输入都放在一起，然后进行排序，按照高度排序，然后再按照操作的情况排序。嗯……然后其实不大会算复杂度的说……NLOGN?

1A的~~~  hiahia 弥补了上一题久debug不过的——不爽……………………

#include <iostream>
#include <stdio.h>
#include <algorithm>
using namespace std;
#define maxn 100100
int sum;
int tree[maxn*5];
struct node
{
    int l,r,z;
    int id,op;
}bri[maxn*2];
int tot[maxn];
int cmp(node a,node b)
{
    if(a.z!=b.z) return a.z<b.z;
    if(a.op!=b.op) return a.op<b.op;
    if(a.l!=b.l) return a.l<b.l;
    return a.r<b.r;
}
void creat(int l,int r,int rt)
{
    tree[rt]=0;
    if(l==r) return;
    int mid=(l+r)/2;
    creat(l,mid,rt<<1);
    creat(mid+1,r,rt<<1|1);
}
void update(int pos,int l,int r,int rt)
{
    if(l==pos&&r==pos)
    {
        tree[rt]++;
        return;
    }
    int mid=(l+r)/2;
    if(pos<=mid) update(pos,l,mid,rt<<1);
    else update(pos,mid+1,r,rt<<1|1);

    tree[rt]=tree[rt<<1]+tree[rt<<1|1];
}
void query(int ll,int rr,int l,int r,int rt)
{
    if(ll==l&&rr==r)
    {
        sum+=tree[rt];
        return;
    }
    int mid=(l+r)/2;
    if(rr<=mid) query(ll,rr,l,mid,rt<<1);
    else if(ll>mid) query(ll,rr,mid+1,r,rt<<1|1);
    else query(ll,mid,l,mid,rt<<1),query(mid+1,rr,mid+1,r,rt<<1|1);
}
int main()
{
    int T,cas=0;
    scanf("%d",&T);
    while(T--)
    {
        int n,m;
        int tmp=0;
        scanf("%d%d",&n,&m);
        int i,j,k;
        for(i=0;i<n;i++)
        {
            scanf("%d",&j);
            bri[i].l=bri[i].r=i;
            bri[i].z=j;
            if(tmp<bri[i].l) tmp=bri[i].l;
            bri[i].op=1;
        }
        int l,r;
        for(i=n;i<n+m;i++)
        {
            scanf("%d%d%d",&l,&r,&j);
            bri[i].l=l;
            bri[i].r=r;
            bri[i].z=j;
            if(tmp<bri[i].r) tmp=bri[i].r;
            bri[i].op=2;
            bri[i].id=i-n;
        }
        int cnt=n+m;
        creat(0,tmp,1);
       /* sort(z,z+cnt);
        int tmp=unique(z,z+cnt)-z;
        for(i=0;i<tmp;i++)
            mp[z[i]]=i;  */
        sort(bri,bri+cnt,cmp);
      //  cout<<endl;for(i=0;i<cnt;i++) printf("%d %d %d *%d\n",bri[i].l,bri[i].r,bri[i].z,bri[i].op);cout<<endl;
        for(i=0;i<cnt;i++)
        {
            if(bri[i].op==1) update(bri[i].l,0,tmp,1);
            else
            {
                sum=0;
                query(bri[i].l,bri[i].r,0,tmp,1);
                tot[bri[i].id]=sum;
            }
        }
        printf("Case %d:\n",++cas);
        for(i=0;i<m;i++) printf("%d\n",tot[i]);
    }
    return 0;
}