81 lines
1.6 KiB
C++
81 lines
1.6 KiB
C++
#include<bits/stdc++.h>
|
|
using namespace std;
|
|
|
|
const int MAX_N=1e6+5;
|
|
int t[MAX_N*10],go[MAX_N*10];
|
|
int n,q,tot=0;
|
|
|
|
int readint();
|
|
void build(int s,int e,int n,int &tot);
|
|
void search(int t[],int s,int e,int n,int l,int r);
|
|
|
|
int main(int argc,char *argv[]){
|
|
#ifdef OITEST
|
|
#define AS(c){if(!(c)){cerr<<"assert failed: "<<#c<<endl;return -1;}}
|
|
AS(argc==3)
|
|
cout<<"TESTING "<<argv[0]<<" "<<argv[1]<<" "<<argv[2]<<endl;
|
|
auto fo = freopen(argv[1],"r",stdin);
|
|
AS(fo!=NULL)
|
|
ifstream afile(argv[2]);
|
|
AS(afile.is_open()==true)
|
|
stringstream ss;
|
|
#define cout ss
|
|
|
|
#endif
|
|
n=readint(),q=readint();
|
|
build(1, n, 1, tot);
|
|
for(int l=1;l<=n;l++){
|
|
for(int r=l;r<=n;r++){
|
|
search(t,1,n,1,l,r);
|
|
}
|
|
}
|
|
|
|
for(int i=1;i<=q;i++){
|
|
int input=readint();
|
|
cout<<t[go[input]]<<endl;
|
|
#ifdef OITEST
|
|
int cans,myans;
|
|
afile>>cans;
|
|
ss>>myans;
|
|
AS(cans==myans)
|
|
#endif
|
|
}
|
|
|
|
}
|
|
|
|
void build(int s,int e,int n,int &tot){
|
|
go[++tot]=n;
|
|
if(s==e){
|
|
return;
|
|
}
|
|
int m=s+(e-s)/2;
|
|
build(s, m, n*2, tot);
|
|
build(m+1,e,n*2+1,tot);
|
|
}
|
|
|
|
void search(int t[],int s,int e,int n,int l,int r){
|
|
if(l<=s&&e<=r){
|
|
t[n]++;
|
|
return;
|
|
}
|
|
if(e<l||r<s){
|
|
return;
|
|
}
|
|
int m=s+(e-s)/2;
|
|
if(l<=m)search(t,s,m,n*2,l,r);
|
|
if(m<r)search(t,m+1,e,n*2+1,l,r);
|
|
}
|
|
|
|
int readint(){
|
|
int x=0,w=1;
|
|
char ch=0;
|
|
while(!isdigit(ch)){
|
|
if(ch=='-')w=-1;
|
|
ch=getchar();
|
|
}
|
|
while(isdigit(ch)){
|
|
x=x*10+(ch-'0');
|
|
ch=getchar();
|
|
}
|
|
return x*w;
|
|
} |