影石Insta360杯-2025牛客暑期多校训练营10 原——[F] Sensei and Yuuka Going Shopping · znzryb
## 思路讲解
思路不能说是一模一样吧，只能说是非常相似。
## AC代码
[https://ac.nowcoder.com/acm/contest/view-submission?submissionId=78887151](https://ac.nowcoder.com/acm/contest/view-submission?submissionId=78887151)
::: 源代码
```cpp
// by Gospel_rock
#include <algorithm>
#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define PB push_back
#define EB emplace_back
#define EM emplace
#define FI first
#define SE second
#define pct __builtin_popcountll
#define ctz __builtin_ctzll
#define SZ(a) ((long long) a.size())
#define FOR(i, a, b) for (long long i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (long long i = (a); i >= (b); --i)
#define debug(var) cerr << #var <<":"<<var<<"\n";
#define cend cerr<<"\n-----------\n"
#define lson(var) (var<<1)
#define rson(var) (var<<1|1)
#define fsp(x) fixed<<setprecision(x)
#define minn(vec) *min_element(vec.begin(),vec.end())
#define maxx(vec) *max_element(vec.begin(),vec.end())
using namespace std;
#ifdef LOCAL
template<typename T> void _print(T x) { cerr << x; }
template<typename T> void _print(vector<T> v) { cerr << "[ "; for (T i : v) _print(i), cerr << " "; cerr << "]"; }
template<typename T> void _print(set<T> s) { cerr << "{ "; for (T i : s) _print(i), cerr << " "; cerr << "}"; }
template<typename T, typename U> void _print(pair<T, U> p) { cerr << "{"; _print(p.first); cerr << ", "; _print(p.second); cerr << "}"; }
template<typename T, typename U> void _print(map<T, U> m) { cerr << "{ "; for (auto &p : m) _print(p), cerr << " "; cerr << "}"; }
#endif
using ll = long long;using ull = unsigned long long;
using DB=double;using LD=long double;
using i128 = __int128;
using pdd = pair<DB,DB>;using plb = pair<ll,bool>;
using pll = pair<ll,ll>;using vll=vector<ll>;using vb=vector<bool>;
using tll = tuple<ll,ll,ll>;using vii=vector<int>;
using vpll = vector<pll>;using vtll = vector<tll>;
using vdb = vector<DB>;using vc=vector<char>;
using arr3 = array<ll,3> ;using arr2 = array<ll,2>;
using CD=complex<double>;
static constexpr ll MAXN=(ll)1e6+10,INF=(ll)1e17+3; // 1e17+3是素数 1e18+9是素数
static constexpr ll mod=(ll)1e9+7; // 998244353;
static constexpr double eps=1e-8;const double pi=acos(-1.0);
ll N,M,Q,X,K,T,lT;
inline void __();
// 来自wida github仓库 https://github.com/hh2048/XCPC/tree/main 加了一些新功能
//46 ms https://acm.hdu.edu.cn/contest/view-code?cid=1179&rid=14912 读入字符getc(a) 的AC记录
// https://www.luogu.com.cn/record/230330447 科学计数法小数，小数
namespace QuickRead { // 快读
char buf[1 << 21], *p1 = buf, *p2 = buf;
inline int getc() {
return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++;
}
template <typename T> void Cin(T &a) {
T ans = 0;
bool f = 0;
char c = getc();
for (; c < '0' || c > '9'; c = getc()) {
if (c == '-') f = 1;
}
for (; c >= '0' && c <= '9'; c = getc()) {
ans = ans * 10 + c - '0';
}
a = f ? -ans : ans;
}
void getc(char &a){
char c=getc();
while (isspace(c)) {
c=getc();
}
a=c;
}
template <typename T> void Cinf(T &a) { // 新增：读取浮点数，支持科学计数法
T ans = 0;
bool f = 0; // 负号
char c = getc();
// 跳过非数字和小数点前的空白/符号
while ((c < '0' || c > '9') && c != '.') {
if (c == '-') f = 1;
c = getc();
}
// 读取整数部分
while (c >= '0' && c <= '9') {
ans = ans * 10 + (c - '0');
c = getc();
}
// 如果有小数点，读取小数部分
if (c == '.') {
c = getc();
T frac = static_cast<T>(1);
while (c >= '0' && c <= '9') {
frac /= 10;
ans += (c - '0') * frac;
c = getc();
}
}
a = f ? -ans : ans;
// 处理科学计数法部分
if (c == 'E' || c == 'e') {
c = getc();
bool exp_neg = false;
if (c == '+') {
c = getc();
} else if (c == '-') {
exp_neg = true;
c = getc();
}
int exp = 0;
while (c >= '0' && c <= '9') {
exp = exp * 10 + (c - '0');
c = getc();
}
T multiplier = pow(10.0, exp_neg ? -exp : exp);
a *= multiplier;
}
}
template <typename T, typename... Args> void Cin(T &a, Args &...args) {
Cin(a), Cin(args...);
}
template <typename T> void write(T x) { // 注意，这里输出不带换行
if (x < 0) putchar('-'), x = -x;
if (x > 9) write(x / 10);
putchar(x % 10 + '0');
}
template <typename T> void writef(T x) { // 新增：输出浮点数，默认输出6位小数，支持四舍五入
if (x < 0) putchar('-'), x = -x;
using ll = long long;
int prec = 6; // 默认精度6，可根据需要调整
// 添加圆整因子
T round_add = static_cast<T>(5);
for (int i = 0; i < prec + 1; ++i) {
round_add /= 10;
}
x += round_add;
ll int_part = static_cast<ll>(x);
write(int_part); // 输出整数部分
putchar('.');
T frac_part = x - int_part;
for (int i = 0; i < prec; ++i) {
frac_part *= 10;
int digit = static_cast<int>(frac_part);
putchar(digit + '0');
frac_part -= digit;
}
}
} // namespace QuickRead
using namespace QuickRead;
// 参考了（抄了）beta99999 的提交 https://www.luogu.com.cn/record/216441078
// 因为自己重写的，目前只支持zkw线段树，配置上只保留了identity
// 采用1-based，闭区间（调用的时候，实际上是0-based左闭右开区间）
// AC https://www.luogu.com.cn/record/231280893 扶苏的问题
// AC https://acm.hdu.edu.cn/contest/view-code?cid=1178&rid=19134 矩形框选卡常
// AC https://ac.nowcoder.com/acm/contest/view-submission?submissionId=78887134 测试_find_l
// AC https://ac.nowcoder.com/acm/contest/view-submission?submissionId=78887151 测试_find_r
template <typename T,typename value_type> struct base_segtree{
int n,sz;
vector<value_type> tr;
static int bit_ceil(int x){int res=1;while(res<x){res<<=1;} return res;};
// zkw线段树开两倍大小，identity为默认值
base_segtree(int n):n(n),sz(bit_ceil(n)),tr((sz<<1),T::identity){}
T *derived() { return static_cast<T*>(this); }
void pushup(int o){
tr[o]=T::op(tr[o<<1],tr[o<<1|1]);
}
value_type val(int o) {
return tr[o];
}
// zkw选配
int dis(int o){return __lg(sz)-__lg(o);} // 倒数第几层？有倒数第0层
int len(int o){return 1<<dis(o);} // （直接调用就可以，就是左闭右开区间长度）
int le(int o){return (o<<dis(o))-sz; } // 左闭
int rr(int o){return (o+1<<dis(o))-sz;} // 右开
// 单节点的下推 在子类中实现
// void pushdown(int o){}
void call_pushdown(int i){ // 把路径上的所有点向下推
int o=i+sz; // 1的__lg(1)=0，相当于就是从根节点慢慢推下来
for(int k=__lg(o);k>=__builtin_ctz(o) + 1;--k){
derived()->pushdown(o>>k);
}
}
void call_pushup(int i){
int o=i+sz;
// 这个下界你可能会很奇怪，为什么不是1？那么答案不在这里，而是在update函数
for(int k=__builtin_ctz(o) + 1;k<=__lg(o);++k){
derived()->pushup(o>>k);
}
}
void build(){
for(int o=sz-1;o>=1;--o){
derived()->pushup(o);
}
}
template<typename D>
void upd(int l,int r,D x){
l--; // 实现1-based -> 0-based
call_pushdown(l),call_pushdown(r);
int l0=l,r0=r;l+=sz,r+=sz;
for(;l<r;l>>=1,r>>=1){
if(l&1) derived()->settag(l++,x);
if(r&1) derived()->settag(--r,x); // 毕竟是右开区间
}
call_pushup(l0);call_pushup(r0);
}
value_type query(int l, int r){
l--;
call_pushdown(l);call_pushdown(r);
l+=sz;r+=sz; // T:: 调用的是类的静态成员，无需实例化
value_type resl=T::identity,resr=T::identity;
for(;l<r;l>>=1,r>>=1){
if(l&1) resl=T::op(resl,val(l++));
if(r&1) resr=T::op(val(--r),resr);
}
return T::op(resl,resr);
}
void assign(int i,value_type a){
i--;
tr[i+sz]=a;
}
template <typename F> int _find_r(int r, F &&fun) { // 找到0-r中fun为true的最后一个数，因为开区间
// r--;
call_pushdown(r), r += sz;
do r >>= __builtin_ctz(r); while (r != 1 && !fun(val(--r)));
if (r == 1) return 0;
while (r < sz) derived()->pushdown(r), r = r << 1 | fun(val(r << 1 | 1));
return r - sz + 1;
}
template <typename F> int _find_l(int l, F &&fun) { // 均为1-based
// l--;
call_pushdown(l), l += sz;
do l >>= __builtin_ctz(l); while (l != 1 && !fun(val(l++)));
if (l == 1) return n;
l--; while (l < sz) derived()->pushdown(l), l = l << 1 | !fun(val(l << 1));
return l - sz + 1;
}
};
struct segtree: base_segtree<segtree, ll> {
static constexpr ll identity = 0;
static ll op(ll a, ll b) { return max(a, b); }
vector<ll> tag;
vector<bool> fixed;
segtree(int n): base_segtree(n), tag(sz), fixed(sz) {}
void settag(int o, pair<int, ll> t) {
int op = t.first;
ll x = t.second;
if (op == 1) {
tr[o] = x;
if (o < sz) tag[o] = 0, fixed[o] = 1;
} else {
tr[o] += x;
if (o < sz && !fixed[o]) tag[o] += x;
}
}
void pushdown(int o) {
if (fixed[o]) {
settag(o << 1, make_pair(1, tr[o]));
settag(o << 1 | 1, make_pair(1, tr[o]));
fixed[o] = 0;
}
if (tag[o]) {
settag(o << 1, make_pair(2, tag[o]));
settag(o << 1 | 1, make_pair(2, tag[o]));
tag[o] = 0;
}
}
};
constexpr ll segtree::identity;
// tr.upd(1,N,(pll){1,0}) 是清空操作
// 采用1-based 索引
// 记得改 identity 默认值为-INF
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
Cin(lT);
while(lT--)
__();
return 0;
}
/*
*/
inline void __(){
Cin(N);
vll A(N+5);
map<ll,vll> Pos;
FOR(i,1,N){
Cin(A[i]);
Pos[A[i]].EB(i);
}
// for(auto &[u,v]:Pos){
// if(SZ(v)<=2) continue;
// }
segtree tr(N+5);
set<ll> vis;
ll ans1=2,ans2=3;
ll ans=0;
FOR(i,1,N-1){
if(SZ(Pos[A[i]])<=2) continue;
if(!vis.count(A[i])){
vis.insert(A[i]);
// 要给中间一个区间留下第二个
tr.upd(Pos[A[i]][1]+1,Pos[A[i]].back(),(pll){2,1});
if(tr.tr[1]>ans){
ans=tr.tr[1];
ans1=i+1;
ans2=tr._find_r(N, [&](ll x){
if(x==ans){
return true;
}
return false;
});
}
}else{
ll id=i;
if(Pos[A[id]].back()==id) continue;
tr.upd(id+1,*(++lower_bound(all(Pos[A[id]]),id)),(pll){2,-1});
// if(Pos[A[id]][SZ(Pos[A[id]])-2]==id){
// tr.upd(id+1,Pos[A[id]].back(),(pll){2,-1});
// b2.erase(Pos[A[id]].back());
// }else{
// tr.upd(id+1,*(++lower_bound(all(Pos[A[id]]),id)),(pll){2,-1});
// }
}
}
// FOR(i,2,N){
// ans=max(ans,tr.ask(i,i));
// }
cout<<ans<<"\n";
cout<<ans1<<" "<<ans2<<"\n";
}
/*
AC
https://ac.nowcoder.com/acm/contest/view-submission?submissionId=78887134
1
9
1 2 3 3 2 1 2 3 1
hack:
1
8
1 1 2 2 2 1 3 1
ans:
1
2 3
*/
```
:::
## 心路历程（WA，TLE，MLE……）