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

#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<map>
using namespace std;
#define int long long
inline int read(){
	int sum(0);
	char ch(getchar());
	for(;ch<'0'||ch>'9';ch=getchar());
	for(;ch>='0'&&ch<='9';sum=sum*10+(ch^48),ch=getchar());
	return sum;
}
typedef long long L;
#define get_size(x) (x?x->size:0)
struct node{
	node *lch,*rch;
	int key,fix;
	L size,weight;
	node(int x=0,int y=0):lch(NULL),rch(NULL),key(x),weight(y),size(y),fix(rand()){}
	inline void pushup(){
		this->size=this->weight+get_size(this->lch)+get_size(this->rch);
	}
}*root;
inline void left_rotate(node *&x){
	node *tmp(x->rch);
	x->rch=tmp->lch;
	tmp->lch=x;
	x->pushup();
	tmp->pushup();
	x=tmp;
}
inline void right_rotate(node *&x){
	node *tmp(x->lch);
	x->lch=tmp->rch;
	tmp->rch=x;
	x->pushup();
	tmp->pushup();
	x=tmp;
}
inline void insert(node *&x,int v,int w){
	if(!x){
		x=new node(v,w);
		return;
	}
	if(v==x->key){
		x->weight+=w;
		x->size+=w;
		return;
	}
	if(v<x->key){
		insert(x->lch,v,w);
		x->pushup();
		if(x->lch->fix<x->fix)
			right_rotate(x);
	}
	else{
		insert(x->rch,v,w);
		x->pushup();
		if(x->rch->fix<x->fix)
			left_rotate(x);
	}
}
inline L qmax(int x){
	node *now(root);
	L ret(0);
	while(now){
		if(now->key<=x)
			now=now->rch;
		else
			ret+=get_size(now->rch)+now->weight,now=now->lch;
	}
	return ret;
}
inline L qmin(int x){
	node *now(root);
	L ret(0);
	while(now){
		if(now->key>=x)
			now=now->lch;
		else
			ret+=get_size(now->lch)+now->weight,now=now->rch;
	}
	return ret;
}
int n,q;
char op[2];
int a[100005];
L pre[100005],nxt[100005],w[100005];
int mx[100005][20];
map<int,L>ma;
inline void ST(){
	for(int i=1;i<=n;++i)
		mx[i][0]=a[i];
	for(int i=1;(1<<i)<=n;++i)
		for(int j=1;j+(1<<i)-1<=n;++j)
			mx[j][i]=max(mx[j][i-1],mx[j+(1<<i-1)][i-1]);
}
inline int querymx(int l,int r){
	int len(r-l+1),k(0);
	while((1<<k)<=len)++k;
	--k;
	return max(mx[l][k],mx[r-(1<<k)+1][k]);
}
inline void cal_pre(int pos){
	int l(1),r(pos-1),mid,ret(-1);
	while(l<=r){
		mid=(l+r)>>1;
		if(querymx(mid,pos-1)<=a[pos])
			r=mid-1,ret=mid;
		else
			l=mid+1;
	}
	if(ret!=-1)
		pre[pos]=pos-ret;
	else
		pre[pos]=0;
}
inline void cal_nxt(int pos){
	int l(pos+1),r(n),mid,ret(-1);
	while(l<=r){
		mid=(l+r)>>1;
		if(querymx(pos+1,mid)<a[pos])
			l=mid+1,ret=mid;
		else
			r=mid-1;
	}
	if(ret!=-1)
		nxt[pos]=ret-pos;
	else
		nxt[pos]=0;
}
signed main(){
	freopen("jxthree.in","r",stdin);
	freopen("jxthree.out","w",stdout);
	n=read(),q=read();
	for(int i=1;i<=n;++i)
		a[i]=read();
	ST();
	for(int i=1;i<=n;++i){
		if(i==1){
			pre[i]=0;
			cal_nxt(1);
			continue;
		}
		if(i==n){
			nxt[i]=0;
			cal_pre(n);
			continue;
		}
		cal_pre(i);
		cal_nxt(i);
	}
	for(int i=1;i<=n;++i){
		w[i]=(pre[i]+1)*(nxt[i]+1);
		ma[a[i]]+=w[i];
	}
	for(int i=1;i<=n;++i)
		insert(root,a[i],w[i]);
	while(q--){
		scanf("%s",op);
		int x(read());
		if(op[0]=='>')
			printf("%lld\n",qmax(x));
		if(op[0]=='='){
			if(!ma.count(x))
				puts("0");
			else
				printf("%lld\n",ma[x]);
		}
		if(op[0]=='<')
			printf("%lld\n",qmin(x));
	}
}