记录编号	459559	评测结果	AAAAAAAAAA
题目名称	学数数	最终得分	100
用户昵称	Anonymity	是否通过	通过
代码语言	C++	运行时间	0.937 s
提交时间	2017-10-13 11:13:03	内存使用	7.94 MiB

#include <cstdio>
#include <iostream>
#include <cstdlib>
#include <algorithm>
#define maxn 100005
#define maxa 400005
using namespace std;
inline void read(int& x)
{	char c=getchar();x=0;int y=1;
	while(c<'0'||c>'9'){if(c=='-') y=-1;c=getchar();}
	while(c>='0'&&c<='9') x=x*10+c-'0',c=getchar();
	x*=y;
}
template<typename T>inline T m_max(T x,T y){return x>y?x:y;}
typedef long long ll;
int n,q,Hashlist[maxn],Hashnum,sz,A[maxn];
ll sum[maxa],all[maxn];
inline int getval(int x){return lower_bound(Hashlist+1,Hashlist+sz+1,x)-Hashlist;}
struct Treap
{	Treap *lch,*rch;int v,r,s,ma,pos;
	Treap(int x=0,int y=0):lch(NULL),rch(NULL),v(x),s(1),r(rand()),ma(x),pos(y){}
	inline int mval(){return this?this->ma:0;}
	inline int val(){return this?this->v:0;}
	inline int sz(){return this?this->s:0;}
	inline void mt()
	{	this->ma=m_max(this->v,m_max(this->lch->mval(),this->rch->mval()));
		this->s=this->lch->sz()+this->rch->sz()+1;
	}
}*root;
typedef pair<Treap*,Treap*> dt;
inline dt split(Treap* x,int k)
{	if(!x) return dt(NULL,NULL);if(!k) return dt(NULL,x);
	dt y;
	if(x->lch->sz()>=k){y=split(x->lch,k);x->lch=y.second;x->mt();y.second=x;return y;}
	else{y=split(x->rch,k-x->lch->sz()-1);x->rch=y.first;x->mt();y.first=x;return y;}
}
inline Treap* merge(Treap* x,Treap* y)
{	if(!x) return y;if(!y) return x;
	if(x->r < y->r){x->rch=merge(x->rch,y);x->mt();return x;}
	else{y->lch=merge(x,y->lch);y->mt();return y;}
}
inline int dfslef(Treap* x,int v)
{	if(!x) return 0;
	if(x->rch->mval()>=v)  return dfslef(x->rch,v);
	else if(x->val()>=v) return x->pos;
	else return dfslef(x->lch,v);
}
inline int dfsrig(Treap* x,int v)
{	if(!x) return 0;
	if(x->lch->mval()>v)  return dfsrig(x->lch,v);
	else if(x->val()>v) return x->pos;
	else return dfsrig(x->rch,v);
}
struct tree{int lc,rc;}tr[maxa];
inline void mt(int z){sum[z]=sum[z<<1]+sum[z<<1|1];}
inline void build(int x,int y,int z)
{	tr[z].lc=x;tr[z].rc=y;
	if(x==y){sum[z]=all[x];return;}
	int mid=x+y>>1;
	build(x,mid,z<<1);build(mid+1,y,z<<1|1);
	mt(z);
}
inline ll query(int x,int y,int z)
{	if(tr[z].lc>=x&&tr[z].rc<=y) return sum[z];
	int mid=tr[z].lc+tr[z].rc>>1;ll tmp=0;
	if(x<=mid) tmp+=query(x,y,z<<1);
	if(mid<y) tmp+=query(x,y,z<<1|1);
	return tmp;
}
inline Treap* fhq_build(int len)
{	Treap* *st=new Treap*[len];Treap *las,*x,*ans;
	int tail=0;
	for(int i=1;i<=len;++i)
	{	x=new Treap(A[i],i);las=NULL;	
		while(tail&&st[tail-1]->r > x->r)
		{	st[tail-1]->mt();las=st[tail-1];
			st[--tail]=NULL;
		}
		if(tail) st[tail-1]->rch=x;
		x->lch=las;
		st[tail++]=x;
	}
	while(tail) st[--tail]->mt();
	ans=st[0];
	delete []st;
	return ans;
}
inline void init()
{	root=fhq_build(n);
	for(int i=1;i<=n;++i)
	{	dt tmp1=split(root,i-1),tmp2=split(tmp1.second,1);
		int t1=0,t2=0;
		if(tmp2.second->mval()<=A[i]) t1=n+1;
		else t1=dfsrig(tmp2.second,A[i]);// pos
		if(tmp1.first->mval()<A[i]) t2=0;
		else t2=dfslef(tmp1.first,A[i]);
		all[getval(A[i])]+=((ll)i-t2)*(ll)(t1-i);
		root=merge(tmp1.first,merge(tmp2.first,tmp2.second));
	}
}
int main()
{	freopen("jxthree.in","r",stdin);
	freopen("jxthree.out","w",stdout);
	read(n);read(q);int x=0;char ord[10];
	for(int i=1;i<=n;++i) read(A[i]),Hashlist[++Hashnum]=A[i];
	sort(Hashlist+1,Hashlist+Hashnum+1);sz=unique(Hashlist+1,Hashlist+Hashnum+1)-Hashlist-1;
	init();
	build(1,sz,1);
	for(int i=1;i<=q;++i)
	{	scanf("%s",ord);read(x);
		if(ord[0]=='>')
		{	int pos=upper_bound(Hashlist+1,Hashlist+sz+1,x)-Hashlist;
			printf("%lld\n",query(pos,sz,1));
		}
		else if(ord[0]=='<')
		{	int pos=getval(x)-1;
			printf("%lld\n",query(1,pos,1));
		}
		else
		{	int pos=getval(x);
			if(Hashlist[pos]!=x) printf("0\n");
			else printf("%lld\n",query(pos,pos,1));
		}
	}
	return 0;
}