- 技术
- 换个角度思考（主席树）
思路：主席树查询区间<=x的和
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <set>
#include<iostream>
#include<vector>
#include<bits/stdc++.h>
using namespace std
;
typedef long long ll
;
#define SIS std::ios::sync_with_stdio(false)
#define space putchar(' ')
#define enter putchar('\n')
#define lson root<<1
#define rson root<<1|1
typedef pair
<int,int> PII
;
const int mod
=1e4+7;
const int N
=2e5+10;
const int inf
=0x7f7f7f7f;
ll
gcd(ll a
,ll b
)
{
return b
==0?a
:gcd(b
,a
%b
);
}
ll
lcm(ll a
,ll b
)
{
return a
*(b
/gcd(a
,b
));
}
template <class T>
void read(T
&x
)
{
char c
;
bool op
= 0;
while(c
= getchar(), c
< '0' || c
> '9')
if(c
== '-')
op
= 1;
x
= c
- '0';
while(c
= getchar(), c
>= '0' && c
<= '9')
x
= x
* 10 + c
- '0';
if(op
)
x
= -x
;
}
template <class T>
void write(T x
)
{
if(x
< 0)
x
= -x
, putchar('-');
if(x
>= 10)
write(x
/ 10);
putchar('0' + x
% 10);
}
int n
,m
,cnt
,root
[N
],a
[N
],x
,y
,k
;
struct node
{
int l
,r
,sum
;
}T
[N
*50];
void update(int l
,int r
,int &x
,int y
,int pos
)
{
T
[++cnt
]=T
[y
];
T
[cnt
].sum
++,x
=cnt
;
if(l
==r
)return ;
int mid
=l
+r
>>1;
if(mid
>=pos
)update(l
,mid
,T
[x
].l
,T
[y
].l
,pos
);
else update(mid
+1,r
,T
[x
].r
,T
[y
].r
,pos
);
}
int query(int l
,int r
,int x
,int y
,int lk
,int rk
)
{
if(r
<=rk
)return T
[y
].sum
-T
[x
].sum
;
int mid
=(l
+r
)/2;
if(rk
<=mid
)return query(l
,mid
,T
[x
].l
,T
[y
].l
,lk
,rk
);
else if(lk
>mid
) return query(mid
+1,r
,T
[x
].r
,T
[y
].r
,lk
,rk
);
else return query(l
,mid
,T
[x
].l
,T
[y
].l
,lk
,mid
)+query(mid
+1,r
,T
[x
].r
,T
[y
].r
,mid
+1,k
);
}
int main()
{
SIS
;
cin
>>n
>>m
;
for(int i
=1;i
<=n
;i
++)
{
cin
>>a
[i
];
}
for(int i
=1;i
<=n
;i
++)
{
update(1,n
,root
[i
],root
[i
-1],a
[i
]);
}
while(m
--)
{
cin
>>x
>>y
>>k
;
int ans
=query(1,n
,root
[x
-1],root
[y
],1,k
);
cout
<<ans
<<endl
;
}
return 0;
}
Processed:
0.016, SQL:
9
