首页 > 代码库 > NYOJ 945 Just do it
NYOJ 945 Just do it
题目链接:http://acm.nyist.net/JudgeOnline/problem.php?pid=945
思路:和hdu3333一个类型的题目。。图灵树,据说很有名~。。
#include <iostream>#include <cstring> #include <algorithm> #include <cstdio>#include <map> #define MAXSIZE 300001using namespace std;struct query_node{ int l,r,index; friend bool operator < (query_node a,query_node b) { return a.r < b.r; } }q[200010];struct node { int l,r; int sum;}tree[MAXSIZE*4];int num[MAXSIZE];void build(int root,int l,int r){ tree[root].sum = 0; tree[root].l = l; tree[root].r = r; if(l==r) { return; } int mid = (l+r)/2; build(root*2,l,mid); build(root*2+1,mid+1,r);}void updata(int root,int pos,int value){ int mid; if(tree[root].l==tree[root].r&&tree[root].l==pos) { tree[root].sum += value; return; } mid = (tree[root].l+tree[root].r)>>1; if(pos<=mid) { updata(root*2,pos,value); } else { updata(root*2+1,pos,value); } tree[root].sum = tree[2*root].sum+tree[2*root+1].sum; return; }int query(int root,int l,int r){ if(tree[root].l>=l&&tree[root].r<=r) { return tree[root].sum; } int mid = (tree[root].r+tree[root].l)/2; if(l>mid) { return query(root*2+1,l,r); } else if(r<=mid) { return query(root*2,l,r); } else { int a = query(root*2,l,mid); int b = query(root*2+1,mid+1,r); return a+b; }}int main(){ //freopen("data.txt","r",stdin); int ans[MAXSIZE]; map<int,int> hash; int t; scanf("%d",&t); while(t--) { int n,m; hash.clear(); scanf("%d",&n); memset(ans,0,sizeof(ans)); build(1,1,n); for(int i=1;i<=n;i++) { scanf("%d",num+i); } scanf("%d",&m); for(int i=0;i<m;i++) { scanf("%d %d",&(q[i].l),&(q[i].r)); q[i].index = i; } sort(q,q+m); int pos = 1; for(int i=0;i<m;i++) { for(;pos<=n&&pos<=q[i].r;pos++) { if(hash[num[pos]]!=0) updata(1,hash[num[pos]],-1); updata(1,pos,1); hash[num[pos]] = pos; } ans[q[i].index] = query(1,q[i].l,q[i].r); } for(int i=0;i<m;i++) { printf("%d\n",ans[i]); } } return 0;}
NYOJ 945 Just do it
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。