| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1347864 | MuhammadSaram | Fire (JOI20_ho_t5) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define ll long long
const int M = 2e5 + 1;
int seg[M*2], fen[M];
void modify(int p,int x)
{
while (p<M)
fen[p]+=x, p+=p&-p;
}
int get(int p)
{
int ans=0;
while (p)
ans+=fen[p], p^=p&-p;
return ans;
}
void solve()
{
int n,m;
cin>>n>>m;
vector<int> v[n+2];
vector<array<int,3>> q[n+1];
int ls=-1;
for (int i=0;i<n;i++)
{
cin>>x;
if (x==2) ls=i;
if (~ls) v[i-ls].push_back(i+1);
}
for (int i=0;i<m;i++)
{
int t,l,r;
cin>>t>>l>>r;
q[t].push_back({l,r,i});
}
int ans[m];
for (int i=0;i<=n;i++)
{
for (int x:v[i]) modify(x,1);
for (auto e:q[i])
ans[e[2]]=get(e[1])-get(e[0]-1)+e[1]-e[0]+1;
}
for (int i=0;i<m;i++)
cout<<ans[i]<<endl;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(NULL), cout.tie(NULL);
int t=1;
// cin>>t;
while (t--)
solve();
return 0;
}