记录编号	459550	评测结果	AAAAAAAAAA
题目名称	学数数	最终得分	100
用户昵称	HZOI_蒟蒻一只	是否通过	通过
代码语言	C++	运行时间	0.473 s
提交时间	2017-10-13 11:09:37	内存使用	2.02 MiB

#include <bits/stdc++.h>
using namespace std;
const int maxn=100005;
#define int long long
long long a[maxn],n,cnt,b[maxn],C[maxn],t[maxn],q;
int lowbit(int x)
{
	return x&(-x);
}
void Modify(int pos,int val)
{
	for(;pos<=cnt;pos+=lowbit(pos))C[pos]+=val;
}
long long Query(int pos)
{
	long long res=0;
	for(;pos;pos-=lowbit(pos))res+=C[pos];
	return res;
}
stack<int>S;
int haha()
{
	freopen("jxthree.in","r",stdin);
	freopen("jxthree.out","w",stdout);
	scanf("%lld%lld",&n,&q);
	for(int i=1;i<=n;i++)scanf("%lld",&a[i]),b[i]=a[i];
	sort(b+1,b+n+1);cnt=unique(b+1,b+n+1)-b-1;
	for(int i=1;i<=n;i++)a[i]=lower_bound(b+1,b+cnt+1,a[i])-b;
	for(int i=1;i<=n;i++)
	{
		while(!S.empty()&&a[S.top()]<=a[i])
		{
			int val=S.top();S.pop();
			int zuo=S.empty()?1:S.top()+1;
			t[a[val]]+=(i-val)*(val-zuo+1);
		}
		S.push(i);
	}
	while(!S.empty())
	{
		int val=S.top();S.pop();
		int zuo=S.empty()?1:S.top()+1;
		t[a[val]]+=(n-val+1)*(val-zuo+1);
	}
	for(int i=1;i<=cnt;i++)Modify(i,t[i]);
	while(q--)
	{
		char opt[3];int val;scanf("%s%lld",opt,&val);
		int bian=lower_bound(b+1,b+cnt+1,val)-b;
		if(b[bian]!=val)
		{
			if(opt[0]=='='){puts("0");continue;}
			if(opt[0]=='<')val=bian;else val=bian-1;
		}
		else val=bian;
		switch(opt[0])
		{
			case '=':printf("%lld\n",Query(val)-Query(val-1));break;
			case '<':printf("%lld\n",Query(val-1));break;
			case '>':printf("%lld\n",n*(n+1)/2-Query(val));break;
		}
	}
}
#undef int
int sb=haha();
int main(){;}