记录编号	459562	评测结果	AAAAAAAAAA
题目名称	学数数	最终得分	100
用户昵称	하루Kiev	是否通过	通过
代码语言	C++	运行时间	1.597 s
提交时间	2017-10-13 11:14:38	内存使用	8.32 MiB

# include "iostream"
# include "stdio.h"
# include "string.h"
# include "algorithm"
# include "math.h"
# define maxn 100005
# define int long long
using namespace std;
int n,q,a[maxn],cnt,Hash,c[maxn*2];
struct query{char c;int no;}e[maxn];
struct sperate{
       int id,s,w;
}v[maxn*2];
int num_cmp(sperate A,sperate B){return A.s<B.s;}
int id_cmp(sperate A,sperate B){return A.id<B.id;}
int check(int now){
    int l=now-1,r=now+1,cnt1=1,cnt2=1;
    while(l>=1){
          if(a[l]>a[now]) break;
          l--;cnt1++;
    }
    while(r<=n){
          if(a[r]>=a[now]) break;
          r++;cnt2++;
    }return cnt1*cnt2;
}
int lowbit(int x){return x&(-x);}
void update(int i,int x){for(i;i<=Hash;i+=lowbit(i))c[i]+=x;}
int sum(int i){int ret=0;for(i;i>0;i-=lowbit(i)) ret+=c[i];return ret;}
int getsum(int x,int y){return sum(y)-sum(x-1);}
signed main(){
	freopen("jxthree.in","r",stdin);
	freopen("jxthree.out","w",stdout);
    scanf("%lld%lld",&n,&q);
    for(int i=1;i<=n;i++){
        cnt++; 
        scanf("%lld",&v[cnt].s);
        v[cnt].id=cnt;
    }
    for(int i=1;i<=q;i++){
        cin>>e[i].c;
        ++cnt;
        scanf("%lld",&v[cnt].s);
        v[cnt].id=cnt;
    }
    sort(v+1,v+1+q+n,num_cmp);
    v[0].s=-1;
    for(int i=1;i<=n+q;i++)
        if(v[i].s!=v[i-1].s) v[i].w=++Hash;
        else v[i].w=Hash;
    sort(v+1,v+1+q+n,id_cmp);
    for(int i=1;i<=n;i++) a[i]=v[i].w;
    for(int i=1;i<=q;i++) e[i].no=v[i+n].w;
    for(int i=1;i<=n;i++) update(a[i],check(i));
    for(int i=1;i<=q;i++){
        if(e[i].c=='>') printf("%lld\n",getsum(e[i].no+1,Hash));
        if(e[i].c=='<') printf("%lld\n",getsum(1,e[i].no-1));
        if(e[i].c=='=') printf("%lld\n",getsum(e[i].no,e[i].no));
    }
}