本文主要是介绍Little Artem and Time Machine CodeForces - 669E，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
http://codeforces.com/problemset/problem/669/E
动态主席树模板题
CDQ分治也可以做 转换为三位偏序 初始给定顺序为第一维 t值为第二维 x值为第三维 代码略
#include <bits/stdc++.h>
using namespace std;struct node1
{int tp;int t;int x;
};struct node2
{int l;int r;int val;
};node1 order[100010];
node2 tree[10000010];
int pret[100010],prex[100010],root[100010];
int q,lent,lenx,num;int lowbit(int x)
{return x&(-x);
}int build(int l,int r)
{int cur,m;cur=num++;if(l==r) return cur;m=(l+r)/2;tree[cur].l=build(l,m);tree[cur].r=build(m+1,r);return cur;
}int updateII(int rot,int tar,int val,int l,int r)
{int cur,m;cur=num++;tree[cur]=tree[rot];tree[cur].val+=val;if(l==r) return cur;m=(l+r)/2;if(tar<=m) tree[cur].l=updateII(tree[rot].l,tar,val,l,m);else tree[cur].r=updateII(tree[rot].r,tar,val,m+1,r);return cur;
}void updateI(int tart,int tarx,int val)
{int i;for(i=tart;i<=lent;i+=lowbit(i)) root[i]=updateII(root[i],tarx,val,1,lenx);
}int queryII(int rot,int tar,int l,int r)
{int m;if(l==r) return tree[rot].val;m=(l+r)/2;if(tar<=m) return queryII(tree[rot].l,tar,l,m);else return queryII(tree[rot].r,tar,m+1,r);
}int queryI(int tart,int tarx)
{int res,i;res=0;for(i=tart;i>=1;i-=lowbit(i)) res+=queryII(root[i],tarx,1,lenx);return res;
}int main()
{int i,pt,px;scanf("%d",&q);for(i=1;i<=q;i++){scanf("%d%d%d",&order[i].tp,&order[i].t,&order[i].x);pret[++lent]=order[i].t;prex[++lenx]=order[i].x;}sort(pret+1,pret+lent+1);sort(prex+1,prex+lenx+1);lent=unique(pret+1,pret+lent+1)-pret-1;lenx=unique(prex+1,prex+lenx+1)-prex-1;root[0]=build(1,lenx);for(i=1;i<=lent;i++) root[i]=root[0];for(i=1;i<=q;i++){pt=lower_bound(pret+1,pret+lent+1,order[i].t)-pret;px=lower_bound(prex+1,prex+lenx+1,order[i].x)-prex;if(order[i].tp==1) updateI(pt,px,1);else if(order[i].tp==2) updateI(pt,px,-1);else printf("%d\n",queryI(pt,px));}return 0;
}
这篇关于Little Artem and Time Machine CodeForces - 669E的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
