记录编号	195913	评测结果	AAAAAAAAAA
题目名称	学数数	最终得分	100
用户昵称	mikumikumi	是否通过	通过
代码语言	C++	运行时间	2.623 s
提交时间	2015-10-20 09:11:02	内存使用	5.66 MiB

#include<cstdio>
#include<deque>
#include<cstring>
#include<iostream>
#include<map>
#include<cmath>
#include<algorithm>
#include<set>
using namespace std;
const int SIZEN=100010,INF=0x7fffffff/2;
typedef long long LL;
deque<LL> P;
map<LL,LL> mp;
multiset<LL> G;
LL N,Q;
LL a[SIZEN]={0};
LL next[SIZEN]={0},be[SIZEN]={0};
LL A[SIZEN]={0};
LL tree[SIZEN]={0};
LL sum=0;
class miku
{
public:
	LL sum,id;
}s[SIZEN];
LL lowbit(int x)
{
	return x&(-x);
}
void add(LL x,LL now)
{
	for(int i=x;i<=N+1;i+=lowbit(i)) tree[i]+=now;
}
void read()
{
	scanf("%lld%lld",&N,&Q);
	for(int i=1;i<=N;i++)
	{
		scanf("%lld",&a[i]);//lld
		G.insert(a[i]);
	}
	G.insert(INF);
	P.push_back(1);
	be[1]=0;
	for(int i=2;i<=N;i++)
	{
		while(!P.empty()&&a[P.back()]<=a[i]) P.pop_back();
		if(!P.empty())
		be[i]=P.back();
		else be[i]=0;
		P.push_back(i);
	}
	P.clear();
	P.push_back(N);
	next[N]=N+1;
	for(int i=N-1;i>=1;i--)
	{
		while(!P.empty()&&a[P.back()]<a[i]) P.pop_back();
		if(!P.empty())
		next[i]=P.back();
		else next[i]=N+1;
		P.push_back(i);
	}
}
bool cmp(miku a,miku b)
{
	return a.sum<b.sum;
}
void make()
{
	for(int i=1;i<=N;i++) s[i].id=i,s[i].sum=a[i];
	sort(s+1,s+N+1,cmp);
	LL cnt=1;
	A[s[1].id]=1;
	mp[s[1].sum]=cnt;
	for(int i=2;i<=N;i++)
	{
		if(s[i].sum!=s[i-1].sum) cnt++;
		mp[s[i].sum]=cnt;
		A[s[i].id]=cnt;
	}
}
void prepare()
{
	make();//离散化
	for(int i=1;i<=N;i++)
	{
		LL now=(i-1-be[i])*(next[i]-i-1);
		now+=(i-1-be[i])+(next[i]-i-1);
		now++;
		sum+=now;
		add(A[i],now);
	}
}
LL get(int x)
{
	LL ans=0;
	for(int i=x;i>0;i-=lowbit(i))
		ans+=tree[i];
	return ans;
}
void work()
{
	char c;
	LL m;
	multiset<LL>::iterator key;
	mp[INF]=N+1;
	mp[0]=0;
	for(int i=1;i<=Q;i++)
	{
		cin>>c;
		scanf("%lld",&m);
		key=G.lower_bound(m);
		int now;
		if(key==G.end()) now=INF;
		else
		{
		while(key!=G.begin()&&*key>m) key--;
		if(*key>m) now=0;
		else now=*key;
		}
		int temm=mp[now];
		//cout<<now<<endl;
		int n=m-1;
		key=G.lower_bound(n);
		if(key==G.end()) now=INF;
		else
		{
		while(key!=G.begin()&&*key>n) key--;
		if(*key>n) now=0;
		else now=*key;
		}
		n=mp[now];
		LL tem1,tem2;
		if(m==0) tem1=0,tem2=0;
		else tem1=get(n),tem2=get(temm);
		LL ans=0;
		//cout<<tem1<<" "<<temm<<endl;
		if(c=='>') ans=sum-tem2;
		else if(c=='=') ans=tem2-tem1;
		else if(c=='<') ans=tem1;
		printf("%lld\n",ans);
	}
}
int main()
{
	freopen("jxthree.in","r",stdin);
	freopen("jxthree.out","w",stdout);
	read();
	prepare();
	work();
	return 0;
}