记录编号	203838	评测结果	AAAAAAAAAA
题目名称	学数数	最终得分	100
用户昵称	/k	是否通过	通过
代码语言	C++	运行时间	0.433 s
提交时间	2015-11-03 18:26:29	内存使用	3.83 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int q[100010],w;
int l;
long long cc[100010];
inline int gl(int a)
{
	return a&(-a);
}
inline void gj(int a,long long s)
{
	while(a<=l)
	{
		cc[a]+=s;
		a+=gl(a);
	}
}
inline long long gs(int a)
{
	long long u=0;
	while(a>0)
	{
		u+=cc[a];
		a-=gl(a);
	}
	return u;
}
struct u
{
	int d;
	int z;
}c[110000];
int y[100010],z[100010],n,m;
int a[100010],s[100010];
inline bool g(const u aa,const u bb)
{
	return aa.z<bb.z;
}
inline int gef(int k)
{
	int z=1,y=l;
	while(z<y)
	{
		int mid=(z+y)>>1;
		if(z==mid)
		    return z;
		if(s[mid]==k)
		    return mid;
		if(s[mid]>k)
		    y=mid;
		else
		    z=mid;
	}
	return z;
}
int main()
{
	freopen("jxthree.in","r",stdin);
	freopen("jxthree.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
	{
		c[i].d=i;
		scanf("%d",&c[i].z);
	}
	sort(c+1,c+1+n,g);
	a[c[1].d]=++l;
	s[1]=c[1].z;
	for(int i=2;i<=n;i++)
	{
		if(c[i].z!=c[i-1].z)
		{
		    l++;
		    s[l]=c[i].z;
		}
		a[c[i].d]=l;
	}
	s[++l]=0x7fffffff;
	for(int i=n;i>=1;i--)
	{
		while(w>0&&a[q[w]]<a[i])
		    w--;
		if(w==0)
		    y[i]=n;
		else
		    y[i]=q[w]-1;
		q[++w]=i;
	}
	w=0;
	for(int i=1;i<=n;i++)
	{
		///////////
		//if(i==2)
		//    printf("%d",q[w]);
		while(w>0&&a[q[w]]<=a[i])
		    w--;
		if(w==0)
		    z[i]=1;
		else
		    z[i]=q[w]+1;
		q[++w]=i;
	}
	/////////////////////
	/*for(int i=1;i<=n;i++)
	    printf("%d ",a[i]);
	    printf("\n");
	for(int i=1;i<=n;i++)
	    printf("%d ",z[i]);
	    printf("\n");
	for(int i=1;i<=n;i++)
	    printf("%d ",y[i]);
	    printf("\n");*/
	for(int i=1;i<=n;i++)
	{
		long long e=(long long)(i-z[i]+1)*(y[i]-i+1);
		gj(a[i],e);
	}
	while(m--)
	{
		char ss[10];
		int k;
		scanf("%s%d",ss,&k);
		if(ss[0]=='=')
		{
			if(k<s[1]||k>=s[l])
			{
				printf("0\n");
				continue;
			}
			int t=gef(k);
			if(s[t]!=k)
			{
				printf("0\n");
				continue;
			}
			printf("%lld\n",gs(t)-gs(t-1));
		}
		else if(ss[0]=='>')
		{
			int t;
			if(k<s[1])
			    t=0;
			else
			    t=gef(k);
			printf("%lld\n",gs(l)-gs(t));
		}
		else
		{
			if(k<s[1])
			{
				printf("0\n");
				continue;
			}
			int t=gef(k);
			if(s[t]==k)
			    t--;
			printf("%lld\n",gs(t));
		}
	}
	return 0;
	/*getchar();
	getchar();*/
	while(1);
}