//******************/
//* I<3 C++ */
//* I WANT ANY AC */
//* I LOVE PROGRAM!*/
//*IT'S INTERESTING*/
//* I LOVE PROGRAM!*/
//* IN CONTESTS */
//* GET SCORE */
//* AC CODE */
//* LET'S */
//* GO */
//* Written by: */
//* Duc Minh */
#include <bits/stdc++.h>
#include <iostream>
#include <cmath>
#include <vector>
#include <map>
#include <set>
#include <stack>
#include <algorithm>
#include <string>
#include <queue>
#include <cctype>
#include <cstring>
#include <iomanip>
#include <deque>
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
using namespace std;
// using namespace __gnu_pbds;
#define file(name) freopen(name".inp", "r", stdin);\
freopen(name".out", "w", stdout);
#define ordered_set tree<ll, null_type,less_equal<ll>, rb_tree_tag,tree_order_statistics_node_update>
#define TIME (1.0 * clock() / CLOCKS_PER_SEC)
#define all(a) a.begin(),a.end()
#define endl "\n"
#define all1(a) a+1,a+n+1
#define unordered_map map
// #define push_back emplace_back
// #define gcd(a,b) __gcd(a,b);
// #define lcm(a,b) (a*b)/gcd(a,b);
const long long INF = (long long)1e9;
const long long MOD = (long long)1e9+7;
const long long MODD = 2017; /// 998244353
const long long maxN = 5e5+9;
const int LOG = 18;
const int mlift = 58;
template<class A> inline int __lg(A &a) { return static_cast<int>(log2(a));}
template<class A,class B> inline void add(A &a,B b) { a+=b;while (a>=MOD) a-=MOD;}
template<class A,class B> inline void minus(A &a,B b) { a-=b;while (a>=MOD) a-=MOD;while (a<0) a+=MOD;}
///--------------------------------
void solve();
signed main(){
// file("BAI4");
long long t;
// cin >> t;
t=1;
while (t--){
solve();
}
cerr << "Time elapsed: " << TIME << "s.\n";
cerr << "ducminh" << "\n";
return 0;
}
///--------------------[PROBLEM SOLUTION]--------------------///
long long tree[maxN*4];
long long a[maxN],vt[maxN],b[maxN],n,q;
void buildtree(long long id, long long l, long long r){
if (l==r){
tree[id]=a[l];
return;
}
long long m=(l+r)>>1;
buildtree(id*2,l,m);
buildtree(id*2+1,m+1,r);
tree[id]=tree[id*2]+tree[id*2+1];
}
void updatetree(long long id, long long l, long long r, long long u, long long v, long long val){
if (u>r || v<l) return;
if (l==r){
tree[id]+=val;
return;
}
long long m=(l+r)>>1;
updatetree(id*2,l,m,u,v,val);
updatetree(id*2+1,m+1,r,u,v,val);
tree[id]=tree[id*2]+tree[id*2+1];
}
long long gettree(long long id, long long l, long long r, long long u, long long v){
if (u>r || v<l) return 0;
if (u<=l && r<=v) return tree[id];
long long m=(l+r)>>1;
return gettree(id*2,l,m,u,v)+gettree(id*2+1,m+1,r,u,v);
}
vector<pair<long long,long long>> luu[500009];
long long ans[500009];
unordered_map<long long,vector<long long>> mm;
void solve(){
cin >> n >> q;
for (int i=1; i<=n; i++){
cin >> a[i];
}
for (int i=1; i<=q; i++){
int l,r;
cin >> l >> r;
luu[l].push_back({r,i});
}
for (int i=n; i>=1; i--){
int sz=0;
if (mm[a[i]].size())
sz=mm[a[i]].size();
if (sz>=1)
if (mm[a[i]][sz-1])
{
updatetree(1,1,n,mm[a[i]][sz-1],mm[a[i]][sz-1],1);
if (sz>=2)
if (mm[a[i]][sz-2]) updatetree(1,1,n,mm[a[i]][sz-2],mm[a[i]][sz-2],-2);
if (sz>=3)
if (mm[a[i]][sz-3]) updatetree(1,1,n,mm[a[i]][sz-3],mm[a[i]][sz-3],1);
}
mm[a[i]].push_back(i);
for (pair<int,int> x: luu[i]){
if (x.first-i==0) ans[x.second]=0;
else
// cout << i << ' ' << x.first << ' ' << gettree(1,1,n,i,x.first) << "\n";
ans[x.second]=max(0LL,gettree(1,1,n,i,x.first));
}
}
for (int i=1; i<=q; i++){
cout << ans[i] << "\n";
}
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
3 ms |
18776 KB |
Output is correct |
| 2 |
Correct |
4 ms |
18780 KB |
Output is correct |
| 3 |
Correct |
6 ms |
18924 KB |
Output is correct |
| 4 |
Correct |
11 ms |
19036 KB |
Output is correct |
| 5 |
Correct |
149 ms |
28500 KB |
Output is correct |
| 6 |
Correct |
160 ms |
28404 KB |
Output is correct |
| 7 |
Correct |
392 ms |
38324 KB |
Output is correct |
| 8 |
Correct |
677 ms |
49260 KB |
Output is correct |
| 9 |
Correct |
889 ms |
54840 KB |
Output is correct |
| 10 |
Correct |
1153 ms |
59452 KB |
Output is correct |
