#1003342 (C++17) No.2849 Birthday Donuts

提出ソース
結果

問題	No.2849 Birthday Donuts
コンテスト
ユーザー	Nachia
提出日時	2024-08-23 22:32:42
言語	C++17 (gcc 13.3.0 + boost 1.87.0)
結果	AC
実行時間	2,582 ms / 6,000 ms
コード長	12,337 bytes
コンパイル時間	2,222 ms
コンパイル使用メモリ	118,516 KB
最終ジャッジ日時	2025-02-24 00:02:52
ジャッジサーバーID （参考情報）	judge2 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン	結果
sample	AC * 1
other	AC * 21
権限があれば一括ダウンロードができます
ソースコード

raw source code
// #ifdef NACHIA
// #define _GLIBCXX_DEBUG
// #else
// #define NDEBUG
// #endif
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using i64 = long long;
using u64 = unsigned long long;
#define rep(i,n) for(int i=0; i<int(n); i++)
const i64 INF = 1001001001001001001;
template<typename A> void chmin(A& l, const A& r){ if(r < l) l = r; }
template<typename A> void chmax(A& l, const A& r){ if(l < r) l = r; }
#include <atcoder/modint>
using Modint = atcoder::static_modint<998244353>;
using namespace std;
#include <cstdint>
#include <utility>

namespace nachia{

int Popcount(unsigned long long c) noexcept {
#ifdef __GNUC__
    return __builtin_popcountll(c);
#else
    c = (c & (~0ull/3)) + ((c >> 1) & (~0ull/3));
    c = (c & (~0ull/5)) + ((c >> 2) & (~0ull/5));
    c = (c & (~0ull/17)) + ((c >> 4) & (~0ull/17));
    c = (c * (~0ull/257)) >> 56;
    return c;
#endif
}

// please ensure x != 0
int MsbIndex(unsigned long long x) noexcept {
#ifdef __GNUC__
    return 63 - __builtin_clzll(x);
#else
    using u64 = unsigned long long;
    int q = (x >> 32) ? 32 : 0;
    auto m = x >> q;
    constexpr u64 hi = 0x8888'8888;
    constexpr u64 mi = 0x1111'1111;
    m = (((m | ~(hi - (m & ~hi))) & hi) * mi) >> 35;
    m = (((m | ~(hi - (x & ~hi))) & hi) * mi) >> 31;
    q += (m & 0xf) << 2;
    q += 0x3333'3333'2222'1100 >> (((x >> q) & 0xf) << 2) & 0xf;
    return q;
#endif
}

// please ensure x != 0
int LsbIndex(unsigned long long x) noexcept {
#ifdef __GNUC__
    return __builtin_ctzll(x);
#else
    return MsbIndex(x & -x);
#endif
}

}


namespace nachia{

template<class PosX, class PosY, class Val>
struct RectangleSum{
private:

struct BitVectorRank {
    using u64 = std::uint64_t;
    using u32 = std::uint32_t;
    
    std::vector<std::pair<u64, u32>> a;
    BitVectorRank(const std::vector<bool>& b = {}){
        int n = b.size();
        a.assign(n/64 + 1, std::make_pair((u64)0, (u32)0));
        auto p = b.begin();
        u32 sum = 0;
        u64 tmp = 0;
        for(int i=0; i<=n; i+=64){
            tmp = 0;
            int maxd = std::min<int>(n - i, 64);
            for(int d=0; d<maxd; d++){
                tmp |= (u64)(*p ? 1 : 0) << d;
                ++p;
            }
            a[i/64] = std::make_pair(tmp, sum);
            sum += Popcount(tmp);
        }
    }
    std::uint32_t rank(std::uint32_t i) const {
        auto [b, s] = a[i >> 6];
        return (u32)(Popcount(b & ~(~u64(0) << (i & 63)))) + s;
    }
    bool get(std::uint32_t i) const { return (a[i >> 6].first >> (i & 63)) & 1; }
};
    
    int n;
    int N;
    int logN;
    std::vector<PosX> Xsorted;
    std::vector<PosY> Ysorted;
    std::vector<int> rankX;
    std::vector<std::vector<Val>> ds;
    std::vector<int> Z;
    std::vector<BitVectorRank> L;
    Val ZERO;
    
    void construct(const std::vector<std::pair<std::pair<PosX, PosY>, Val>>& val){
        n = val.size();

        std::vector<std::pair<PosX,PosY>> pos(n);
        for(int i=0; i<n; i++) pos[i] = val[i].first;

        std::vector<int> sortIY(n);
        for(int i=0; i<n; i++) sortIY[i] = i;
        std::sort(sortIY.begin(),sortIY.end(),[&pos](int l,int r){
            return pos[l].second < pos[r].second; });
        Ysorted.resize(n);
        for(int i=0; i<n; i++) Ysorted[i] = pos[sortIY[i]].second;

        std::vector<int> sortIX(n);
        rankX.resize(n);
        for(int i=0; i<n; i++) sortIX[i] = i;
        std::sort(sortIX.begin(),sortIX.end(),[&pos](int l,int r){
            return pos[l]<pos[r]; });
        Xsorted.resize(n);
        for(int i=0; i<n; i++) Xsorted[i] = pos[sortIX[i]].first;
        for(int i=0; i<n; i++) rankX[sortIX[i]] = i;

        N = 1; logN = 0;
        while(N < n){ N *= 2; logN++; }
        ds.assign(logN+1, std::vector<Val>(n+1, ZERO));
        L.resize(logN);
        Z.resize(logN);
        std::vector<int> Idx = sortIY;
        for(int k=0; k<n; k++) ds[logN][k+1] = ds[logN][k] + val[Idx[k]].second;
        for(int i=logN-1; i>=0; i--){
            std::vector<bool> Lbuf(n,0);
            std::vector<int> preIdx(n); std::swap(preIdx, Idx);
            int z = ((n >> (i+1)) << i) + std::min(1<<i, (n % (2 << i)));
            Z[i] = z;
            int ai = 0, bi = z;
            for(int k=0; k<n; k++){
                bool chooseb = rankX[preIdx[k]] & (1<<i);
                if(!chooseb) Idx[ai++] = preIdx[k];
                else Idx[bi++] = preIdx[k];
                Lbuf[k] = !chooseb;
            }
            for(int k=0; k<n; k++) ds[i][k+1] = ds[i][k] + val[Idx[k]].second;
            L[i] = BitVectorRank(Lbuf);
        }

        for(int i=0; i<n; i++) rankX[sortIY[i]] = i;
    }

public:

    RectangleSum(const std::vector<std::pair<std::pair<PosX, PosY>, Val>>& val, Val Zero)
        : ZERO(Zero) {
        construct(val);
    }

    RectangleSum(const std::vector<std::pair<PosX, PosY>>& points, const std::vector<Val>& vals, Val Zero)
        : ZERO(Zero) {
        n = vals.size();
        std::vector<std::pair<std::pair<PosX, PosY>, Val>> buf;
        for(int i=0; i<n; i++) buf.emplace_back(points[i], vals[i]);
    }

    Val sumByIndex(int xl, int xr, int yl, int yr){
        Val ans = ZERO;
        if(xl >= xr || yl >= yr) return ans;
        struct Search{ int i, xa, xb, ys, yt; };
        std::vector<Search> Q;
        Q.reserve((logN+1)*2);
        Q.push_back({ logN,0,n,yl,yr });
        for(int i=0; i<(int)Q.size(); i++){
            auto p = Q[i];
            if(p.xa == p.xb) continue;
            if(xl <= p.xa && p.xb <= xr){
                ans += ds[p.i][p.yt] - ds[p.i][p.ys];
                continue;
            }
            p.i--;
            int nxs = L[p.i].rank(p.ys), nxt = L[p.i].rank(p.yt);
            int xm = p.xa+(1<<p.i);
            if(xl < xm) Q.push_back({ p.i,p.xa,xm,nxs,nxt });
            if(xm < xr) Q.push_back({ p.i,xm,p.xb,Z[p.i]+p.ys-nxs,Z[p.i]+p.yt-nxt });
        }
        return ans; 
    }
  
    Val sum(PosX xl, PosX xr, PosY yl, PosY yr){
        return sumByIndex(
            lower_bound(Xsorted.begin(),Xsorted.end(),xl) - Xsorted.begin(),
            lower_bound(Xsorted.begin(),Xsorted.end(),xr) - Xsorted.begin(),
            lower_bound(Ysorted.begin(),Ysorted.end(),yl) - Ysorted.begin(),
            lower_bound(Ysorted.begin(),Ysorted.end(),yr) - Ysorted.begin()
        );
    }

    Val sumLUByIndex(int xr, int yr){
        if(xr == n) return ds[logN][yr];
        Val ans = ZERO;
        int xa = 0, xb = n, ys = 0, yt = yr;
        for(int i=logN; i>=1; ){
            if(xa == xb) break;
            i--;
            int nxs = L[i].rank(ys), nxt = L[i].rank(yt);
            int xm = xa + (1<<i);
            if(xr < xm){
                xb = xm; ys = nxs; yt = nxt;
            } else {
                ans += ds[i][nxt] - ds[i][nxs];
                xa = xm; ys = Z[i]+ys-nxs; yt = Z[i]+yt-nxt;
            }
        }
        return ans; 
    }
  
    Val sumLU(PosX xr, PosY yr){
        return sumLUByIndex(
            lower_bound(Xsorted.begin(),Xsorted.end(),xr) - Xsorted.begin(),
            lower_bound(Ysorted.begin(),Ysorted.end(),yr) - Ysorted.begin()
        );
    }
};

} // namespace nachia
#include <cassert>



namespace nachia{

namespace prime_sieve_explicit_internal{
    std::vector<bool> isprime = { false }; // a[x] := isprime(2x+1)

    void CalcIsPrime(int z){
        if((int)isprime.size() *2+1 < z+1){
            int new_z = isprime.size();
            while(new_z*2+1 < z+1) new_z *= 2;
            z = new_z-1;
            isprime.resize(z+1, true);
            for(int i=1; i*(i+1)*2<=z; i++) if(isprime[i]){
                for(int j=i*(i+1)*2; j<=z; j+=i*2+1) isprime[j] = false;
            }
        }
    }
    
    std::vector<int> prime_list = {2};
    int prime_list_max = 0;

    void CalcPrimeList(int z){
        while((int)prime_list.size() < z){
            if((int)isprime.size() <= prime_list_max + 1) CalcIsPrime(prime_list_max * 2 + 10);
            for(int p=prime_list_max+1; p<(int)isprime.size(); p++){
                if(isprime[p]) prime_list.push_back(p*2+1);
            }
            prime_list_max = isprime.size() - 1;
        }
    }

    void CalcPrimeListUntil(int z){
        if(prime_list_max < z){
            CalcIsPrime(z);
            for(int p=prime_list_max+1; p<(int)isprime.size(); p++){
                if(isprime[p]) prime_list.push_back(p*2+1);
            }
            prime_list_max = isprime.size() - 1;
        }
    }

}


bool IsprimeExplicit(int n){
    using namespace prime_sieve_explicit_internal;
    if(n == 2) return true;
    if(n % 2 == 0) return false;
    CalcIsPrime(n);
    return isprime[(n-1)/2];
}

int NthPrimeExplicit(int n){
    using namespace prime_sieve_explicit_internal;
    CalcPrimeList(n);
    return prime_list[n];
}

int PrimeCountingExplicit(int n){
    using namespace prime_sieve_explicit_internal;
    if(n < 2) return 0;
    CalcPrimeListUntil(n);
    auto res = std::upper_bound(prime_list.begin(), prime_list.end(), n) - prime_list.begin();
    return (int)res;
}

// [l, r)
std::vector<bool> SegmentedSieveExplicit(long long l, long long r){
    assert(0 <= l); assert(l <= r);
    long long d = r - l;
    if(d == 0) return {};
    std::vector<bool> res(d, true);
    for(long long p=2; p*p<=r; p++) if(IsprimeExplicit(p)){
        long long il = (l+p-1)/p, ir = (r+p-1)/p;
        if(il <= p) il = p;
        for(long long i=il; i<ir; i++) res[i*p-l] = false;
    }
    if(l < 2) for(long long p=l; p<2 && p<r; p++) res[l-p] = false;
    return res;
}


} // namespace nachia

namespace nachia{

template<class Elem>
void DivisorZeta(std::vector<Elem>& a){
    int n = a.size() - 1;
    for(int d=2; d<=n; d++) if(IsprimeExplicit(d)) for(int i=1; i*d<=n; i++) a[i*d] += a[i];
}

template<class Elem>
void DivisorReversedZeta(std::vector<Elem>& a){
    int n = a.size() - 1;
    for(int d=2; d<=n; d++) if(IsprimeExplicit(d)) for(int i=n/d; i>=1; i--) a[i] += a[i*d];
}

template<class Elem>
void DivisorMobius(std::vector<Elem>& a){
    int n = a.size() - 1;
    for(int d=2; d<=n; d++) if(IsprimeExplicit(d)) for(int i=n/d; i>=1; i--) a[i*d] -= a[i];
}

template<class Elem>
void DivisorReversedMobius(std::vector<Elem>& a){
    int n = a.size() - 1;
    for(int d=2; d<=n; d++) if(IsprimeExplicit(d)) for(int i=1; i*d<=n; i++) a[i] -= a[i*d];
}

template<class Elem>
std::vector<Elem> GcdConvolution(std::vector<Elem> a, std::vector<Elem> b){
    assert(a.size() == b.size());
    assert(1 <= a.size());
    DivisorReversedZeta(a);
    DivisorReversedZeta(b);
    for(int i=1; i<(int)a.size(); i++) a[i] *= b[i];
    DivisorReversedMobius(a);
    return a;
}

template<class Elem>
std::vector<Elem> LcmConvolution(std::vector<Elem> a, std::vector<Elem> b){
    assert(a.size() == b.size());
    assert(1 <= a.size());
    DivisorZeta(a);
    DivisorZeta(b);
    for(int i=1; i<(int)a.size(); i++) a[i] *= b[i];
    DivisorMobius(a);
    return a;
}

template<class Elem>
void SumForCoprimeIndex(std::vector<Elem>& f){
    if((int)f.size() <= 1) return;
    Elem q = f[1];
    for(int i=2; i<(int)f.size(); i++) q += f[i];
    std::vector<int> F(f.size()); F[1] = -1;
    DivisorMobius(F);
    DivisorReversedZeta(f);
    f[1] -= f[1];
    Elem t = f[1];
    for(int i=2; i<(int)f.size(); i++){
        if(F[i] == 0) f[i] = f[1];
        if(F[i] == -1){ t = f[1]; t -= f[i]; f[i] = t; }
    }
    DivisorZeta(f);
    for(int i=1; i<(int)f.size(); i++){ t = q; t -= f[i]; f[i] = t; }
}

} // namespace nachia

void testcase(){
    int Z = 200000;
    vector<int> Q(Z+1);
    for(int i=1; i<=Z; i++) Q[i] = i-1;
    nachia::DivisorMobius(Q);
    vector<pair<int,int>> pos;
    vector<i64> weight;
    vector<pair<pair<int,int>, i64>> pw;
    for(int p=2; p<=Z; p++) for(int q=2; q*p<=Z; q++){
        pos.push_back({ p*q-p, p*q });
        weight.push_back(Q[p]);
        pw.push_back({ pos.back(), weight.back() });
    }
    auto md = nachia::RectangleSum<int,int,i64>(pw, 0);
    int T; cin >> T;
    i64 ansxor = 0;
    rep(t,T){
        i64 l,r; cin >> l >> r; l ^= ansxor; r ^= ansxor;
        i64 s = md.sum(l, r+1, l, r+1);
        i64 ans = r*(r-1)/2 - (l-1)*(l-2)/2 - s;
        ansxor = ans;
        cout << ans << '\n';
    }
}

int main(){
    ios::sync_with_stdio(false); cin.tie(nullptr);
    testcase();
    return 0;
}
yukicoder

結果

ソースコード
