Решал эту задачу, но ТЛ-ится
Вот код:
#include <iostream>
#include <iomanip>
#include <vector>
#include <string>
#include <map>
#include <algorithm>
#include <cmath>
#include <queue>
#include <set>
#include <bitset>
#include <climits>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <time.h>
#include <stdio.h>
#include <stack>
#include <unordered_map>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define pb push_back
#define sz(x) (int)x.size()
#define mispertion ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define F first
#define S second
#define getlast(s) (*s.rbegin())
#define debg cout<<"OK\n"
const double PI = 3.1415926535;
const int N = 1e5 + 1;
const int mod = 998244353;
const int infi = INT_MAX;
const ll infl = LLONG_MAX;
int mult(int a, int b)
{
return a * 1LL * b % mod;
}
int sum(int a, int b)
{
if(a + b < 0)
return a + b + mod;
if(a + b >= mod)
return a + b - mod;
return a + b;
}
ll binpow(ll a, ll n)
{
if (n == 0)
return 1;
if (n % 2 == 1){
return binpow(a, n - 1) * a;
}
else
{
ll b = binpow(a, n / 2);
return b * b;
}
}
int gcd(int a, int b)
{
if (a == 0)
return b;
if (b == 0)
return a;
if (a > b)
return gcd(a % b, b);
return gcd(a, b % a);
}
struct sparset{
vector<vector<int>> t;
void init(vector<int> &a, int n){
t.assign(20, vector<int>(n));
for(int i = 0; i < n; i++)
t[0][i] = a[i];
for(int l = 1; l < 20; l++)
for(int i = 0; i + (1 << l) <= n; i++)
t[l][i] = gcd(t[l - 1][i], t[l - 1][i + (1 << (l - 1))]);
}
int get(int l, int r){
int p = __lg(r - l);
return gcd(t[p][l], t[p][r - (1 << p)]);
}
} t;
vector<int> f(int n, vector<int> &a, int len){
vector<int> ret;
multiset<int> mn;
for(int i = 0; i < len - 1; i++){
mn.insert(a[i]);
}
for(int i = 0; i + len - 1 < n; i++){
mn.insert(a[i + len - 1]);
if(i != 0)
mn.erase(mn.find(a[i - 1]));
int l = i, r = i + len - 1;
int nodik = t.get(l, r + 1);
if(nodik % (*mn.begin()) == 0)
ret.pb(l);
}
return ret;
}
int main()
{
mispertion;
int n;
cin >> n;
vector<int> a(n);
for(int i = 0; i < n; i++)
cin >> a[i];
t.init(a, n);
int lo = 1, hi = n + 1;
while(lo + 1 < hi){
int m = (lo + hi) / 2;
if(f(n, a, m).size() != 0)
lo = m;
else
hi = m;
}
vector<int> ans = f(n, a, lo);
cout << ans.size() << ' ' << lo - 1 << '\n';
for(auto e : ans){
cout << e + 1 << '\n';
}
return 0;
}
Решение примитивное, бинарил можно ли сделать отрезок какой то длинны x, в функции f проверял само условие перебирая отрезки длинны x, параллельно в мультисете хранил текущий минимум и с помощью разреженной таблицы считал НОД, если НОД делится на минимум значит отрезок подходит. Вроде все работает за O(nlog²n), ± 10^8 операций, мб можно как то еще оптимизировать или вообще надо менять идею?
