0%

影石Insta360杯-2025牛客暑期多校训练营10 原——[F] Sensei and Yuuka Going Shopping

Posted on 2025-08-16 Edited on 2026-02-18

思路讲解

思路不能说是一模一样吧，只能说是非常相似。

AC代码

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=78887151

源代码

// 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……）