#include <cstdio>
#include <cassert>
#include <vector>
#include <algorithm>
#define let const auto
#define rep(name,beg,end) for(auto lim_##name = end,name = beg;name <= lim_##name;name++)
#define per(name,beg,end) for(auto lim_##name = end,name = beg;name >= lim_##name;name--)
#define repn(lim) for(auto REPN_lIM = lim,REPN = 1;REPN <= REPN_lIM;REPN++)
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define trace() debug("line : %d, Function : %s\n",__LINE__,__FUNCTION__)
constexpr int maxn = 5e5 + 100;
int n,q,val[maxn],ans[maxn];
std::vector<int> pos[maxn];
void discretize(){
static int tmp[maxn];
std::copy_n(val + 1,n,tmp + 1);
std::sort(tmp + 1,tmp + 1 + n);
let tot = std::unique(tmp + 1,tmp + 1 + n) - tmp - 1;
rep(i,1,n)val[i] = std::lower_bound(tmp + 1,tmp + 1 + tot,val[i]) - tmp;
}
namespace fenwick{
int f[maxn];
constexpr int lowbit(const int x){return x & (-x);}
void add(int pos,const int v){
for(;pos <= n;pos += lowbit(pos))f[pos] += v;
}
int query(int pos){
int res = 0;
for(;pos;pos -= lowbit(pos))res += f[pos];
return res;
}
}
struct Event{int opt,id,x,y,v;};
std::vector<Event> events;
void ins(const int lx,const int rx,const int ly,const int ry){
events.push_back(Event{1,0,lx,ly,1});
events.push_back(Event{1,0,rx + 1,ly,-1});
events.push_back(Event{1,0,lx,ry + 1,-1});
events.push_back(Event{1,0,rx + 1,ry + 1,1});
}
int main(){
// std::freopen("poklon.in","r",stdin);
// std::freopen("poklon.out","w",stdout);
std::scanf("%d %d",&n,&q);
rep(i,1,n)std::scanf("%d",val + i);
discretize();
rep(i,1,n)pos[val[i]].push_back(i);
rep(v,1,n){
let &pos = ::pos[v];
for(size_t i = 1;i < pos.size();i++){
let p = pos[i - 1],q = pos[i];
let pre = i == 1 ? 1 : pos[i - 2] + 1;
let nxt = i + 1 == pos.size() ? n : pos[i + 1] - 1;
ins(pre,p,q,nxt);
}
}
rep(id,1,q){
int l,r; std::scanf("%d %d",&l,&r);
events.push_back(Event{0,id,l,r,0});
}
std::sort(events.begin(),events.end(),[](const Event &a,const Event &b){
if(a.x != b.x)return a.x < b.x;
return a.opt > b.opt;
});
for(let &e : events)
if(e.opt == 1)fenwick::add(e.y,e.v);
else ans[e.id] = fenwick::query(e.y);
rep(i,1,q)std::printf("%d\n",ans[i]);
std::fclose(stdin);
std::fclose(stdout);
return 0;
}
Compilation message
poklon.cpp: In function 'int main()':
poklon.cpp:46:12: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
46 | std::scanf("%d %d",&n,&q);
| ~~~~~~~~~~^~~~~~~~~~~~~~~
poklon.cpp:47:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
47 | rep(i,1,n)std::scanf("%d",val + i);
| ~~~~~~~~~~^~~~~~~~~~~~~~
poklon.cpp:60:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
60 | int l,r; std::scanf("%d %d",&l,&r);
| ~~~~~~~~~~^~~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
7 ms |
12116 KB |
Output is correct |
| 2 |
Correct |
7 ms |
12116 KB |
Output is correct |
| 3 |
Correct |
7 ms |
12244 KB |
Output is correct |
| 4 |
Correct |
11 ms |
12944 KB |
Output is correct |
| 5 |
Correct |
108 ms |
25616 KB |
Output is correct |
| 6 |
Correct |
109 ms |
25700 KB |
Output is correct |
| 7 |
Correct |
235 ms |
39616 KB |
Output is correct |
| 8 |
Correct |
373 ms |
59164 KB |
Output is correct |
| 9 |
Correct |
469 ms |
67748 KB |
Output is correct |
| 10 |
Correct |
618 ms |
104284 KB |
Output is correct |
