Hope you enjoy those tasks!↵
↵
[problem:1332A]↵
↵
<spoiler summary="Tutorial">↵
[tutorial:132732A]↵
</spoiler>↵
↵
<spoiler summary="Solution (python by pikmike)">↵
↵
~~~~~↵
t = int(input())↵
for _ in range(t):↵
a, b, c, d = map(int, input().split())↵
x, y, x1, y1, x2, y2 = map(int, input().split())↵
x += b - a↵
y += d - c↵
if a + b > 0 and x1 == x2:↵
print("No")↵
elif c + d > 0 and y1 == y2:↵
print("No")↵
elif x1 <= x <= x2 and y1 <= y <= y2:↵
print("Yes")↵
else:↵
print("No")↵
~~~~~↵
↵
↵
</spoiler>↵
↵
<spoiler summary="Solution (C++)">↵
↵
~~~~~↵
#include<bits/stdc++.h>↵
using namespace std;↵
↵
int a,b,c,d,x,y,x1,y1,x2,y2,xx,yy;↵
↵
int main(){↵
int t;↵
cin>>t;↵
while (t--){↵
cin>>a>>b>>c>>d;↵
cin>>x>>y>>x1>>y1>>x2>>y2;↵
xx=x,yy=y;↵
x+=-a+b, y+=-c+d;↵
if (x>=x1&&x<=x2&&y>=y1&&y<=y2&&(x2>x1||a+b==0)&&(y2>y1||c+d==0)){↵
cout<<"Yes\n";↵
}↵
else{↵
cout<<"No\n";↵
}↵
}↵
return 0;↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
[problem:1332B]↵
↵
<spoiler summary="Tutorial">↵
[tutorial:1332B]↵
</spoiler>↵
↵
<spoiler summary="Solution (python by pikmike)">↵
↵
~~~~~↵
from math import gcd↵
↵
def getprime(x):↵
for i in range(2, x):↵
if x % i == 0:↵
return i↵
return -1↵
↵
primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31]↵
↵
t = int(input())↵
for _ in range(t):↵
n = int(input())↵
a = [int(x) for x in input().split()]↵
used = [False for i in range(11)]↵
clr = []↵
for i in range(n):↵
x = primes.index(getprime(a[i]))↵
used[x] = True↵
clr.append(x)↵
cnt = 0↵
num = []↵
for i in range(11):↵
num.append(cnt)↵
if used[i]:↵
cnt += 1↵
print(cnt)↵
for i in range(n):↵
x = primes.index(getprime(a[i]))↵
print(num[x] + 1, end = " ")↵
print()↵
~~~~~↵
↵
↵
</spoiler>↵
↵
<spoiler summary="Solution (C++)">↵
↵
~~~~~↵
#include<bits/stdc++.h>↵
using namespace std;↵
↵
int n,t;↵
vector<int> ans[1007];↵
int res[1007];↵
int main(){↵
ios::sync_with_stdio(false);↵
cin.tie(0), cout.tie(0);↵
auto f=[&](int u){↵
for (int i=2;i<=u;++i){↵
if (u%i==0) return i;↵
}↵
};↵
cin>>t;↵
while (t--){↵
cin>>n;↵
for (int i=1;i<=1000;++i) ans[i].clear();↵
for (int i=1;i<=n;++i){↵
int u;↵
cin>>u; ans[f(u)].push_back(i);↵
}↵
int ret=0;↵
for (int i=1;i<=1000;++i){↵
if (ans[i].size()){↵
++ret;↵
for (auto c:ans[i]){↵
res[c]=ret;↵
}↵
}↵
}↵
cout<<ret<<"\n";↵
for (int i=1;i<=n;++i){↵
cout<<res[i]<<" ";↵
}↵
cout<<"\n";↵
}↵
return 0;↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
[problem:1332C]↵
↵
<spoiler summary="Tutorial">↵
[tutorial:1332C]↵
</spoiler>↵
↵
<spoiler summary="Solution(C++)">↵
↵
~~~~~↵
from sys import stdin↵
↵
t = int(stdin.readline())↵
for _ in range(t):↵
n, k = map(int, stdin.readline().split())↵
s = stdin.readline()↵
cnt = [[0 for i in range(26)] for j in range((k + 1) // 2)]↵
for i in range(n):↵
cnt[min(i % k, k - i % k - 1)][ord(s[i]) - ord('a')] += 1↵
ans = 0↵
for i in range(k // 2):↵
ans += 2 * n // k - max(cnt[i])↵
if k % 2 == 1:↵
ans += n // k - max(cnt[k // 2])↵
print(ans)↵
~~~~~↵
↵
</spoiler>↵
↵
<spoiler summary="Solution(C++)">↵
↵
~~~~~↵
#include<bits/stdc++.h>↵
using namespace std;↵
↵
const int maxn=200007;↵
↵
int n,k,ans=0;↵
int cnt[maxn][26];↵
string s;↵
↵
int differ(int u,int v){↵
int ret=0,mx=0;↵
for (int j=0;j<26;++j){↵
ret+=cnt[u][j]+cnt[v][j];↵
mx=max(mx,cnt[u][j]+cnt[v][j]);↵
}↵
return ret-mx;↵
}↵
↵
int main(){↵
int t;↵
cin>>t;↵
while (t--){↵
cin>>n>>k>>s;↵
for (int i=0;i<k;++i){↵
for (int j=0;j<26;++j){↵
cnt[i][j]=0;↵
}↵
}↵
for (int i=0;i<n;++i){↵
cnt[i%k][s[i]-'a']++;↵
}↵
int ans=0;↵
for (int i=0;i<k;++i){↵
ans+=differ(i,k-1-i);↵
}↵
cout<<ans/2<<"\n";↵
}↵
return 0;↵
}↵
~~~~~↵
↵
</spoiler>↵
↵
[problem:1332D]↵
↵
<spoiler summary="Tutorial">↵
[tutorial:1332D]↵
</spoiler>↵
↵
<spoiler summary="Solution(python by pikmike)">↵
↵
~~~~~↵
k = int(input())↵
x = 2**17↵
print(2, 3)↵
print(x^k, x, 0)↵
print(k, x^k, k)↵
~~~~~↵
↵
</spoiler>↵
↵
[problem:1332E]↵
↵
<spoiler summary="Tutorial">↵
[tutorial:1332E]↵
</spoiler>↵
↵
<spoiler summary="Solution 1(python by pikmike)">↵
↵
~~~~~↵
MOD = 998244353↵
↵
n, m, l, r = map(int, input().split())↵
if n * m % 2 == 1:↵
print(pow(r - l + 1, n * m, MOD))↵
elif (r - l + 1) % 2 == 0:↵
print(pow(r - l + 1, n * m, MOD) * (MOD + 1) // 2 % MOD)↵
else:↵
print((pow(r - l + 1, n * m, MOD) + 1) * (MOD + 1) // 2 % MOD)↵
~~~~~↵
↵
</spoiler>↵
↵
<spoiler summary="Solution 2(python by pikmike)">↵
↵
~~~~~↵
MOD = 998244353↵
↵
n, m, l, r = map(int, input().split())↵
if n * m % 2 == 1:↵
print(pow(r - l + 1, n * m, MOD))↵
else:↵
e = r // 2 - (l - 1) // 2 ↵
o = (r - l + 1) - e↵
print((pow(e + o, n * m, MOD) + pow(e - o, n * m, MOD)) * (MOD + 1) // 2 % MOD)↵
~~~~~↵
↵
</spoiler>↵
↵
[problem:1332F]↵
↵
<spoiler summary="Tutorial">↵
[tutorial:1332F]↵
</spoiler>↵
↵
<spoiler summary="Solution(C++)">↵
↵
~~~~~↵
#include<bits/stdc++.h>↵
#define int long long↵
#define ULL unsigned long long↵
#define F first↵
#define S second↵
#define pb push_back↵
#define rep(i,n) for(int i=0;i<(int)(n);++i)↵
#define rep1(i,n) for(int i=1;i<=(int)(n);++i)↵
#define range(a) a.begin(), a.end()↵
#define PI pair<int,int>↵
#define VI vector<int>↵
#define debug cout<<"potxdy"<<endl; ↵
using namespace std;↵
↵
typedef long long ll;↵
↵
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());↵
↵
const int maxn=300007;↵
const int mod=998244353;↵
↵
int n,dp[maxn][2],f[maxn]; ↵
VI vec[maxn];↵
↵
int mult(int u,int v){↵
u=(u%mod+mod)%mod, v=(v%mod+mod)%mod;↵
return 1ll*u*v%mod;↵
}↵
↵
void dfs(int u,int p){↵
dp[u][0]=dp[u][1]=f[u]=1;↵
for (auto c:vec[u]){↵
if (c==p) continue;↵
dfs(c,u);↵
dp[u][0]=mult(dp[u][0],2*dp[c][0]+2*dp[c][1]-f[c]);↵
dp[u][1]=mult(dp[u][1],dp[c][1]+2*dp[c][0]-f[c]);↵
f[u]=mult(f[u],dp[c][0]+dp[c][1]-f[c]);↵
}↵
}↵
↵
#undef int↵
int main(){↵
ios::sync_with_stdio(false);↵
cin.tie(0), cout.tie(0);↵
cin>>n;↵
for (int i=1;i<n;++i){↵
int u,v;↵
cin>>u>>v;↵
vec[u].pb(v), vec[v].pb(u);↵
}↵
dfs(1,0);↵
cout<<(dp[1][0]+dp[1][1]-f[1]-1+2*mod)%mod<<endl;↵
return 0;↵
}↵
~~~~~↵
↵
</spoiler>↵
↵
↵
[problem:1332G]↵
↵
Contributor of idea of the solution: [user:pikmike,2020-03-24]↵
↵
<spoiler summary="Tutorial">↵
[tutorial:1332G]↵
</spoiler>↵
↵
<spoiler summary="Solution (C++)">↵
↵
~~~~~↵
#include<bits/stdc++.h>↵
↵
using namespace std;↵
↵
const int maxn=200007;↵
int n,q,a[maxn],b[maxn],c[maxn],t[maxn],sum[maxn];↵
int st1[maxn],st2[maxn],p1,p2,r1,r2,s1,s2;↵
int ans1[maxn][4],ans2[maxn][4];↵
set<int> s;↵
↵
bool cmp1(int u,int v){↵
return a[u]<a[v];↵
}↵
↵
bool cmp2(int u,int v){↵
return a[u]>a[v];↵
}↵
↵
int main(){↵
ios::sync_with_stdio(false);↵
cin.tie(0), cout.tie(0);↵
cin>>n>>q;↵
for (int i=1;i<=n;++i){↵
cin>>a[i];↵
}↵
p1=p2=r1=r2=0;↵
s.insert(n+1);↵
for (int i=n;i>0;--i){↵
while (p1){↵
int u=st1[p1];↵
if (a[u]>a[i]){↵
t[u]--;↵
if (!t[u]) s.insert(u);↵
p1--;↵
r1=0;↵
}↵
else{↵
break;↵
}↵
}↵
while (p2){↵
int u=st2[p2];↵
if (a[u]<a[i]){↵
t[u]--;↵
if (!t[u]) s.insert(u);↵
p2--;↵
r2=0;↵
}↵
else{↵
break;↵
}↵
}↵
s1=lower_bound(st1+1,st1+p1+1,i,cmp1)-st1-1, s2=lower_bound(st2+1,st2+p2+1,i,cmp2)-st2-1;↵
b[i]=i+max(r1,r2)+1;↵
ans1[i][0]=i, ans1[i][1]=b[i]-1, ans1[i][2]=b[i];↵
if (s1&&s2){↵
c[i]=*s.lower_bound(max(st1[s1],st2[s2]));↵
if (c[i]<=n){↵
int u=lower_bound(st1+1,st1+p1+1,c[i],greater<int>())-st1,v=lower_bound(st2+1,st2+p2+1,c[i],greater<int>())-st2;↵
ans2[i][0]=i, ans2[i][1]=min(st1[u],st2[v]), ans2[i][2]=max(st1[u],st2[v]), ans2[i][3]=c[i];↵
}↵
}↵
else{↵
c[i]=n+1;↵
}↵
st1[++p1]=i;↵
st2[++p2]=i;↵
r1++, r2++;↵
t[i]+=2;↵
if (i<n&&b[i]>b[i+1]){↵
b[i]=b[i+1];↵
for (int j=0;j<3;++j){↵
ans1[i][j]=ans1[i+1][j];↵
}↵
}↵
if (i<n&&c[i]>c[i+1]){↵
c[i]=c[i+1];↵
for (int j=0;j<4;++j){↵
ans2[i][j]=ans2[i+1][j];↵
}↵
}↵
}↵
while (q--){↵
int l,r;↵
cin>>l>>r;↵
if (r>=c[l]){↵
cout<<"4\n";↵
for (int j=0;j<4;++j){↵
cout<<ans2[l][j]<<" ";↵
}↵
cout<<"\n";↵
}↵
else{↵
if (r>=b[l]){↵
cout<<"3\n";↵
for (int j=0;j<3;++j){↵
cout<<ans1[l][j]<<" ";↵
}↵
cout<<"\n";↵
}↵
else{↵
cout<<"0\n\n";↵
}↵
}↵
}↵
return 0; ↵
}↵
~~~~~↵
↵
</spoiler>↵
↵
↵
[problem:1332A]↵
↵
<spoiler summary="Tutorial">↵
[tutorial:13
</spoiler>↵
↵
<spoiler summary="Solution (python by pikmike)">↵
↵
~~~~~↵
t = int(input())↵
for _ in range(t):↵
a, b, c, d = map(int, input().split())↵
x, y, x1, y1, x2, y2 = map(int, input().split())↵
x += b - a↵
y += d - c↵
if a + b > 0 and x1 == x2:↵
print("No")↵
elif c + d > 0 and y1 == y2:↵
print("No")↵
elif x1 <= x <= x2 and y1 <= y <= y2:↵
print("Yes")↵
else:↵
print("No")↵
~~~~~↵
↵
↵
</spoiler>↵
↵
<spoiler summary="Solution (C++)">↵
↵
~~~~~↵
#include<bits/stdc++.h>↵
using namespace std;↵
↵
int a,b,c,d,x,y,x1,y1,x2,y2,xx,yy;↵
↵
int main(){↵
int t;↵
cin>>t;↵
while (t--){↵
cin>>a>>b>>c>>d;↵
cin>>x>>y>>x1>>y1>>x2>>y2;↵
xx=x,yy=y;↵
x+=-a+b, y+=-c+d;↵
if (x>=x1&&x<=x2&&y>=y1&&y<=y2&&(x2>x1||a+b==0)&&(y2>y1||c+d==0)){↵
cout<<"Yes\n";↵
}↵
else{↵
cout<<"No\n";↵
}↵
}↵
return 0;↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
[problem:1332B]↵
↵
<spoiler summary="Tutorial">↵
[tutorial:1332B]↵
</spoiler>↵
↵
<spoiler summary="Solution (python by pikmike)">↵
↵
~~~~~↵
from math import gcd↵
↵
def getprime(x):↵
for i in range(2, x):↵
if x % i == 0:↵
return i↵
return -1↵
↵
primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31]↵
↵
t = int(input())↵
for _ in range(t):↵
n = int(input())↵
a = [int(x) for x in input().split()]↵
used = [False for i in range(11)]↵
clr = []↵
for i in range(n):↵
x = primes.index(getprime(a[i]))↵
used[x] = True↵
clr.append(x)↵
cnt = 0↵
num = []↵
for i in range(11):↵
num.append(cnt)↵
if used[i]:↵
cnt += 1↵
print(cnt)↵
for i in range(n):↵
x = primes.index(getprime(a[i]))↵
print(num[x] + 1, end = " ")↵
print()↵
~~~~~↵
↵
↵
</spoiler>↵
↵
<spoiler summary="Solution (C++)">↵
↵
~~~~~↵
#include<bits/stdc++.h>↵
using namespace std;↵
↵
int n,t;↵
vector<int> ans[1007];↵
int res[1007];↵
int main(){↵
ios::sync_with_stdio(false);↵
cin.tie(0), cout.tie(0);↵
auto f=[&](int u){↵
for (int i=2;i<=u;++i){↵
if (u%i==0) return i;↵
}↵
};↵
cin>>t;↵
while (t--){↵
cin>>n;↵
for (int i=1;i<=1000;++i) ans[i].clear();↵
for (int i=1;i<=n;++i){↵
int u;↵
cin>>u; ans[f(u)].push_back(i);↵
}↵
int ret=0;↵
for (int i=1;i<=1000;++i){↵
if (ans[i].size()){↵
++ret;↵
for (auto c:ans[i]){↵
res[c]=ret;↵
}↵
}↵
}↵
cout<<ret<<"\n";↵
for (int i=1;i<=n;++i){↵
cout<<res[i]<<" ";↵
}↵
cout<<"\n";↵
}↵
return 0;↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
[problem:1332C]↵
↵
<spoiler summary="Tutorial">↵
[tutorial:1332C]↵
</spoiler>↵
↵
<spoiler summary="Solution(C++)">↵
↵
~~~~~↵
from sys import stdin↵
↵
t = int(stdin.readline())↵
for _ in range(t):↵
n, k = map(int, stdin.readline().split())↵
s = stdin.readline()↵
cnt = [[0 for i in range(26)] for j in range((k + 1) // 2)]↵
for i in range(n):↵
cnt[min(i % k, k - i % k - 1)][ord(s[i]) - ord('a')] += 1↵
ans = 0↵
for i in range(k // 2):↵
ans += 2 * n // k - max(cnt[i])↵
if k % 2 == 1:↵
ans += n // k - max(cnt[k // 2])↵
print(ans)↵
~~~~~↵
↵
</spoiler>↵
↵
<spoiler summary="Solution(C++)">↵
↵
~~~~~↵
#include<bits/stdc++.h>↵
using namespace std;↵
↵
const int maxn=200007;↵
↵
int n,k,ans=0;↵
int cnt[maxn][26];↵
string s;↵
↵
int differ(int u,int v){↵
int ret=0,mx=0;↵
for (int j=0;j<26;++j){↵
ret+=cnt[u][j]+cnt[v][j];↵
mx=max(mx,cnt[u][j]+cnt[v][j]);↵
}↵
return ret-mx;↵
}↵
↵
int main(){↵
int t;↵
cin>>t;↵
while (t--){↵
cin>>n>>k>>s;↵
for (int i=0;i<k;++i){↵
for (int j=0;j<26;++j){↵
cnt[i][j]=0;↵
}↵
}↵
for (int i=0;i<n;++i){↵
cnt[i%k][s[i]-'a']++;↵
}↵
int ans=0;↵
for (int i=0;i<k;++i){↵
ans+=differ(i,k-1-i);↵
}↵
cout<<ans/2<<"\n";↵
}↵
return 0;↵
}↵
~~~~~↵
↵
</spoiler>↵
↵
[problem:1332D]↵
↵
<spoiler summary="Tutorial">↵
[tutorial:1332D]↵
</spoiler>↵
↵
<spoiler summary="Solution(python by pikmike)">↵
↵
~~~~~↵
k = int(input())↵
x = 2**17↵
print(2, 3)↵
print(x^k, x, 0)↵
print(k, x^k, k)↵
~~~~~↵
↵
</spoiler>↵
↵
[problem:1332E]↵
↵
<spoiler summary="Tutorial">↵
[tutorial:1332E]↵
</spoiler>↵
↵
<spoiler summary="Solution 1(python by pikmike)">↵
↵
~~~~~↵
MOD = 998244353↵
↵
n, m, l, r = map(int, input().split())↵
if n * m % 2 == 1:↵
print(pow(r - l + 1, n * m, MOD))↵
elif (r - l + 1) % 2 == 0:↵
print(pow(r - l + 1, n * m, MOD) * (MOD + 1) // 2 % MOD)↵
else:↵
print((pow(r - l + 1, n * m, MOD) + 1) * (MOD + 1) // 2 % MOD)↵
~~~~~↵
↵
</spoiler>↵
↵
<spoiler summary="Solution 2(python by pikmike)">↵
↵
~~~~~↵
MOD = 998244353↵
↵
n, m, l, r = map(int, input().split())↵
if n * m % 2 == 1:↵
print(pow(r - l + 1, n * m, MOD))↵
else:↵
e = r // 2 - (l - 1) // 2 ↵
o = (r - l + 1) - e↵
print((pow(e + o, n * m, MOD) + pow(e - o, n * m, MOD)) * (MOD + 1) // 2 % MOD)↵
~~~~~↵
↵
</spoiler>↵
↵
[problem:1332F]↵
↵
<spoiler summary="Tutorial">↵
[tutorial:1332F]↵
</spoiler>↵
↵
<spoiler summary="Solution(C++)">↵
↵
~~~~~↵
#include<bits/stdc++.h>↵
#define int long long↵
#define ULL unsigned long long↵
#define F first↵
#define S second↵
#define pb push_back↵
#define rep(i,n) for(int i=0;i<(int)(n);++i)↵
#define rep1(i,n) for(int i=1;i<=(int)(n);++i)↵
#define range(a) a.begin(), a.end()↵
#define PI pair<int,int>↵
#define VI vector<int>↵
#define debug cout<<"potxdy"<<endl; ↵
using namespace std;↵
↵
typedef long long ll;↵
↵
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());↵
↵
const int maxn=300007;↵
const int mod=998244353;↵
↵
int n,dp[maxn][2],f[maxn]; ↵
VI vec[maxn];↵
↵
int mult(int u,int v){↵
u=(u%mod+mod)%mod, v=(v%mod+mod)%mod;↵
return 1ll*u*v%mod;↵
}↵
↵
void dfs(int u,int p){↵
dp[u][0]=dp[u][1]=f[u]=1;↵
for (auto c:vec[u]){↵
if (c==p) continue;↵
dfs(c,u);↵
dp[u][0]=mult(dp[u][0],2*dp[c][0]+2*dp[c][1]-f[c]);↵
dp[u][1]=mult(dp[u][1],dp[c][1]+2*dp[c][0]-f[c]);↵
f[u]=mult(f[u],dp[c][0]+dp[c][1]-f[c]);↵
}↵
}↵
↵
#undef int↵
int main(){↵
ios::sync_with_stdio(false);↵
cin.tie(0), cout.tie(0);↵
cin>>n;↵
for (int i=1;i<n;++i){↵
int u,v;↵
cin>>u>>v;↵
vec[u].pb(v), vec[v].pb(u);↵
}↵
dfs(1,0);↵
cout<<(dp[1][0]+dp[1][1]-f[1]-1+2*mod)%mod<<endl;↵
return 0;↵
}↵
~~~~~↵
↵
</spoiler>↵
↵
↵
[problem:1332G]↵
↵
Contributor of idea of the solution: [user:pikmike,2020-03-24]↵
↵
<spoiler summary="Tutorial">↵
[tutorial:1332G]↵
</spoiler>↵
↵
<spoiler summary="Solution (C++)">↵
↵
~~~~~↵
#include<bits/stdc++.h>↵
↵
using namespace std;↵
↵
const int maxn=200007;↵
int n,q,a[maxn],b[maxn],c[maxn],t[maxn],sum[maxn];↵
int st1[maxn],st2[maxn],p1,p2,r1,r2,s1,s2;↵
int ans1[maxn][4],ans2[maxn][4];↵
set<int> s;↵
↵
bool cmp1(int u,int v){↵
return a[u]<a[v];↵
}↵
↵
bool cmp2(int u,int v){↵
return a[u]>a[v];↵
}↵
↵
int main(){↵
ios::sync_with_stdio(false);↵
cin.tie(0), cout.tie(0);↵
cin>>n>>q;↵
for (int i=1;i<=n;++i){↵
cin>>a[i];↵
}↵
p1=p2=r1=r2=0;↵
s.insert(n+1);↵
for (int i=n;i>0;--i){↵
while (p1){↵
int u=st1[p1];↵
if (a[u]>a[i]){↵
t[u]--;↵
if (!t[u]) s.insert(u);↵
p1--;↵
r1=0;↵
}↵
else{↵
break;↵
}↵
}↵
while (p2){↵
int u=st2[p2];↵
if (a[u]<a[i]){↵
t[u]--;↵
if (!t[u]) s.insert(u);↵
p2--;↵
r2=0;↵
}↵
else{↵
break;↵
}↵
}↵
s1=lower_bound(st1+1,st1+p1+1,i,cmp1)-st1-1, s2=lower_bound(st2+1,st2+p2+1,i,cmp2)-st2-1;↵
b[i]=i+max(r1,r2)+1;↵
ans1[i][0]=i, ans1[i][1]=b[i]-1, ans1[i][2]=b[i];↵
if (s1&&s2){↵
c[i]=*s.lower_bound(max(st1[s1],st2[s2]));↵
if (c[i]<=n){↵
int u=lower_bound(st1+1,st1+p1+1,c[i],greater<int>())-st1,v=lower_bound(st2+1,st2+p2+1,c[i],greater<int>())-st2;↵
ans2[i][0]=i, ans2[i][1]=min(st1[u],st2[v]), ans2[i][2]=max(st1[u],st2[v]), ans2[i][3]=c[i];↵
}↵
}↵
else{↵
c[i]=n+1;↵
}↵
st1[++p1]=i;↵
st2[++p2]=i;↵
r1++, r2++;↵
t[i]+=2;↵
if (i<n&&b[i]>b[i+1]){↵
b[i]=b[i+1];↵
for (int j=0;j<3;++j){↵
ans1[i][j]=ans1[i+1][j];↵
}↵
}↵
if (i<n&&c[i]>c[i+1]){↵
c[i]=c[i+1];↵
for (int j=0;j<4;++j){↵
ans2[i][j]=ans2[i+1][j];↵
}↵
}↵
}↵
while (q--){↵
int l,r;↵
cin>>l>>r;↵
if (r>=c[l]){↵
cout<<"4\n";↵
for (int j=0;j<4;++j){↵
cout<<ans2[l][j]<<" ";↵
}↵
cout<<"\n";↵
}↵
else{↵
if (r>=b[l]){↵
cout<<"3\n";↵
for (int j=0;j<3;++j){↵
cout<<ans1[l][j]<<" ";↵
}↵
cout<<"\n";↵
}↵
else{↵
cout<<"0\n\n";↵
}↵
}↵
}↵
return 0; ↵
}↵
~~~~~↵
↵
</spoiler>↵
↵
