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

#include <fstream>
#include <map>
#include <algorithm>
#include <vector>
#include <set>
#define N 100010
using namespace std;
typedef long long ll;
ifstream in("jxthree.in");
ofstream out("jxthree.out");
int n,q,L=1;
ll a[N]={0},ans=0,INF=1;
ll c[N]={0},SL[N]={0},SR[N]={0};
vector<ll> Q;
set<ll > O,W;
map<ll,int> T;
class rantostack//单调栈
{
public:
	int m;
	int num[N];
	int pos[N];
	void clear(){m=0;}
	void push(int x,int y){m++;num[m]=x;pos[m]=y;}
	int top_first(){return num[m];}
	int top_second(){return pos[m];}
	int size(){return m;}
	void pop(){m--;}
}S;
class range
{
public:
	int lc,rc;
	int name,pos;
	range(){lc=rc=name=-1;}
}b[N];
void read()
{
	int i;
	in>>n>>q;
	INF=(INF<<57);
	for(i=1;i<=n;i++)
	{
		in>>a[i];
		if(!T[a[i]])
		{
			T[a[i]]=1;
			Q.push_back(a[i]);
		}
	}
	Q.push_back(INF);
	sort(Q.begin(),Q.end());
	L=Q.size()-1;
	for(i=0;i<L;i++)T[Q[i]]=i+1;
}
ll count(range x)//"统治"范围
{
	ll l,r,sum;
	l=x.pos-x.lc;
	r=x.rc-x.pos;
	sum=(l+1)*(r+1);
	return sum;
}
void init()
{
	int i,j,u,v;
	ll l,r;
	S.clear();
	for(i=1;i<=n;i++)
	{
		while(S.size())
		{
			u=S.top_first();
			v=S.top_second();
			if(a[i]>u)b[v].rc=i-1;
			else break;
			S.pop();
		}
		S.push(a[i],i);
	}
	S.clear();
	for(i=n;i>=1;i--)
	{
		while(S.size())
		{
			u=S.top_first();
			v=S.top_second();
			if(a[i]>=u)b[v].lc=i+1;
			else break;
			S.pop();
		}
		S.push(a[i],i);
	}
	for(i=1;i<=n;i++)
	{
		if(b[i].lc==-1)b[i].lc=1;
		if(b[i].rc==-1)b[i].rc=n;
		b[i].name=a[i];
		b[i].pos=i;
	}
	for(i=1;i<=n;i++)
	{
		u=T[b[i].name];
		c[u]+=count(b[i]);
	}
	for(i=1;i<=L;i++)SL[i]=SL[i-1]+c[i];//前缀和
	for(i=L;i>=1;i--)SR[i]=SR[i+1]+c[i];//后缀和
}
void work()
{
	char link;
	ll ask,u,ans;
	set<ll>::iterator it;
	int i,x;
	for(i=0;i<L;i++)
	{
		u=Q[i];
		O.insert(u);
		W.insert(-u);
	}
	for(i=1;i<=q;i++)
	{
		in>>link>>ask;
		if(link=='<')
		{
			it=W.upper_bound(-ask);
			u=-*it;
			x=T[u];
            ans=SL[x];
		}
		if(link=='=')
		{
			x=T[ask];
			if(x)ans=c[x];
			else ans=0;
		}
		if(link=='>')
		{
			it=O.upper_bound(ask);
			x=T[*it];
			ans=SR[x];
		}
		out<<ans<<endl;
	}
}
int main()
{
	read();
	init();
	work();
	return 0;
}