题意在这里~

http://absi2011.is-programmer.com/posts/202524.html

写了个treap来维护..理论上是能做到强制在线的..

感觉treap很多时候能维护一些splay能维护的东西..包括当线段树用..

代码:

#include<set>
#include<map>
#include<list>
#include<queue>
#include<stack>
#include<math.h>
#include<string>
#include<time.h>
#include<bitset>
#include<vector>
#include<memory>
#include<utility>
#include<stdio.h>
#include<sstream>
#include<fstream>
#include<iostream>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
using namespace std;
struct nodes
{
    int ty;
    int t;
    int x;
    int id;
    friend bool operator < (const nodes &a,const nodes &b)
    {
        if (a.x!=b.x) return a.x<b.x;
        return a.id<b.id;
    }
    void read()
    {
        scanf("%d%d%d",&ty,&t,&x);
    }
};
nodes a[100005];
int b[100005];
struct node
{
    int val;
    int weight;
    int sum;
    int val2;
    node * ch[2];
};
node * null;
node * new_node(int x1=0,int x2=0)
{
    static node a[100005];
    static int top=0;
    node * t=&a[top++];
    t->val=x1;
    t->weight=rand();
    t->sum=x2;
    t->val2=x2;
    t->ch[0]=null;
    t->ch[1]=null;
    return t;
}
int ans[100005];
void rotate(node * &x,int c)
{
    node * y=x->ch[c];
    x->ch[c]=y->ch[!c];
    y->ch[!c]=x;
    y->sum=x->sum;
    x->sum=x->ch[0]->sum+x->ch[1]->sum+x->val2;
    x=y;
}
void insert(node * &now,node * x)
{
    if (now==null)
    {
        now=x;
        return;
    }
    now->sum+=x->val2;
    int c;
    if (x->val>now->val) c=1; else c=0;
    insert(now->ch[c],x);
    if (x->weight>now->weight) rotate(now,c);
}
int query(node * now,int val)
{
    if (now==null) return 0;
    if (val<now->val)
    {
        return query(now->ch[0],val);
    }
    else
    {
        return query(now->ch[1],val)+now->ch[0]->sum+now->val2;
    }
}
int main()
{
    #ifdef absi2011
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    #endif
    null=new_node();
    null->weight=-1;
    null->ch[0]=null;
    null->ch[1]=null;
    int n;
    scanf("%d",&n);
    int i;
    for (i=0;i<n;i++)
    {
        a[i].read();
        a[i].id=i;
        b[i]=a[i].t;
    }
    sort(a,a+n);
    sort(b,b+n);
    for (i=0;i<n;i++)
    {
        a[i].t=lower_bound(b,b+n,a[i].t)-b;
    }
    node * root;
    for (i=0;i<n;i++)
    {
        if ((i==0)||(a[i].x!=a[i-1].x))
        {
            root=null;
        }
        if (a[i].ty==1)
        {
            insert(root,new_node(a[i].t,1));
            ans[a[i].id]=-1;
        }
        if (a[i].ty==2)
        {
            insert(root,new_node(a[i].t,-1));
            ans[a[i].id]=-1;
        }
        if (a[i].ty==3)
        {
            ans[a[i].id]=query(root,a[i].t);
        }
    }
    for (i=0;i<n;i++)
    {
        if (ans[i]==-1) continue;
        printf("%d\n",ans[i]);
    }
    return 0;
}