题意:
同上
题解:
抓着这题作死的搞~~是因为今天练习赛的一道题.SPOJ KQUERY.直到我用最后一种树状数组通过了HDOJ这题后..交SPOJ的才没超时..看排名...时间能排到11名了..有些叼...看下时间效率..自下而上: 划分树、线段树、树状数组、优化后的树状数组...
划分树的效率最低...看来划分树的应用范围还是是很有局限性...只在求kth number的时候给力..逆过来求就已经力不从心了...
线段树及树状数组处理本题..需要把询问都存下来...按照询问数从小到大按排个序..并且把每个数以及其序号存下来..按数字从小到大排个序...首先这一列数都是空的(全0)..然后边放数边统计结果...
Program: 线段树171MS
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<cmath>
#include<queue>
#include<stack>
#include<set>
#include<map>
#include<algorithm>
#define ll long long
#define eps 1e-5
#define oo 1000000007
#define pi acos(-1.0)
#define MAXN 100005
using namespace std;
struct node
{
int x,w;
}p[MAXN];
struct question
{
int l,r,x,id;
}q[200005];
int sum[MAXN<<2],ans[200005];
void update(int p,int x,int l,int r,int now)
{
if (l==r) { sum[now]=x; return; }
int mid=l+r>>1;
if (p<=mid) update(p,x,l,mid,now<<1);
if (p>mid) update(p,x,mid+1,r,now<<1|1);
sum[now]=sum[now<<1]+sum[now<<1|1];
return;
}
int query(int L,int R,int l,int r,int now)
{
if (L<=l && R>=r) return sum[now];
int mid=l+r>>1,ans=0;
if (L<=mid) ans+=query(L,R,l,mid,now<<1);
if (R>mid) ans+=query(L,R,mid+1,r,now<<1|1);
return ans;
}
bool cmp1(node a,node b) { return a.x<b.x; }
bool cmp2(question a,question b) { return a.x<b.x; }
int main()
{
int n,m,i,x,t,h,T,cases;
scanf("%d",&T);
for (cases=1;cases<=T;cases++)
{
printf("Case %d:\n",cases);
scanf("%d%d",&n,&m);
for (i=1;i<=n;i++) scanf("%d",&p[i].x),p[i].w=i;
sort(p+1,p+1+n,cmp1);
p[n+1].x=oo;
for (i=1;i<=m;i++)
{
scanf("%d%d%d",&q[i].l,&q[i].r,&q[i].x);
q[i].l++,q[i].r++;
q[i].id=i;
}
sort(q+1,q+1+m,cmp2);
memset(sum,0,sizeof(sum));
h=x=1;
while (x<=n && h<=m)
{
t=p[x].x;
while (p[x].x==t) update(p[x].w,1,1,n,1),x++;
while (h<=m && q[h].x<t) ans[q[h].id]=0,h++;
while (h<=m && q[h].x<p[x].x)
ans[q[h].id]=query(q[h].l,q[h].r,1,n,1),h++;
}
for (i=1;i<=m;i++) printf("%d\n",ans[i]);
}
return 0;
}
Program: 树状数组 125MS
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<cmath>
#include<queue>
#include<stack>
#include<set>
#include<map>
#include<algorithm>
#define ll long long
#define eps 1e-5
#define oo 1000000007
#define pi acos(-1.0)
#define MAXN 100005
using namespace std;
struct node
{
int x,w;
}p[MAXN];
struct question
{
int l,r,x,id;
}q[200005];
int sum[MAXN],ans[200005],n;
void insert(int x,int k)
{
while (k<=n)
{
sum[k]+=x;
k+=k&(-k);
}
return;
}
int query(int k)
{
int ans=0;
while (k)
{
ans+=sum[k];
k-=k&(-k);
}
return ans;
}
bool cmp1(node a,node b) { return a.x<b.x; }
bool cmp2(question a,question b) { return a.x<b.x; }
int main()
{
int m,i,x,t,h,T,cases;
scanf("%d",&T);
for (cases=1;cases<=T;cases++)
{
printf("Case %d:\n",cases);
scanf("%d%d",&n,&m);
for (i=1;i<=n;i++) scanf("%d",&p[i].x),p[i].w=i;
sort(p+1,p+1+n,cmp1);
p[n+1].x=oo;
for (i=1;i<=m;i++)
{
scanf("%d%d%d",&q[i].l,&q[i].r,&q[i].x);
q[i].l++,q[i].r++;
q[i].id=i;
}
sort(q+1,q+1+m,cmp2);
memset(sum,0,sizeof(sum));
h=x=1;
while (x<=n && h<=m)
{
t=p[x].x;
while (p[x].x==t) insert(1,p[x].w),x++;
while (h<=m && q[h].x<t) ans[q[h].id]=0,h++;
while (h<=m && q[h].x<p[x].x)
ans[q[h].id]=query(q[h].r)-query(q[h].l-1),h++;
}
for (i=1;i<=m;i++) printf("%d\n",ans[i]);
}
return 0;
}
Program: 树状数组 78MS
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<cmath>
#include<queue>
#include<stack>
#include<set>
#include<map>
#include<algorithm>
#define ll long long
#define eps 1e-5
#define oo 1000000007
#define pi acos(-1.0)
#define MAXN 100005
#define MAXM 200005
using namespace std;
struct node
{
int x,w;
}p[MAXN];
int sum[MAXN],ans[200005],n,ql[MAXM],qr[MAXM],qx[MAXM],qid[MAXM];
void insert(int x,int k)
{
while (k<=n)
{
sum[k]+=x;
k+=k&(-k);
}
return;
}
int query(int k)
{
int ans=0;
while (k)
{
ans+=sum[k];
k-=k&(-k);
}
return ans;
}
int input()
{
char c;
do
{
c=getchar();
}while (c<'0' || c>'9');
int d=0;
while (c>='0' && c<='9')
{
d=d*10+c-'0';
c=getchar();
}
return d;
}
bool cmp1(node a,node b) { return a.x<b.x; }
bool cmp2(int a,int b) { return qx[a]<qx[b]; }
int main()
{
int m,i,x,t,h,T,cases;
scanf("%d",&T);
for (cases=1;cases<=T;cases++)
{
printf("Case %d:\n",cases);
scanf("%d%d",&n,&m);
for (i=1;i<=n;i++) p[i].x=input(),p[i].w=i;
sort(p+1,p+1+n,cmp1);
p[n+1].x=oo;
for (i=1;i<=m;i++)
{
ql[i]=input()+1,qr[i]=input()+1,qx[i]=input();
qid[i]=i;
}
sort(qid+1,qid+1+m,cmp2);
memset(sum,0,sizeof(sum));
h=x=1;
while (x<=n && h<=m)
{
t=p[x].x;
while (p[x].x==t) insert(1,p[x].w),x++;
while (h<=m && qx[qid[h]]<t) ans[qid[h]]=0,h++;
while (h<=m && qx[qid[h]]<p[x].x)
ans[qid[h]]=query(qr[qid[h]])-query(ql[qid[h]]-1),h++;
}
for (i=1;i<=m;i++) printf("%d\n",ans[i]);
}
return 0;
}