#1105897 (C++17) No.3207 Digital Font

• 問題: No.3207 Digital Font
• ユーザー: GOTKAKO
• 提出日時: 2025-07-19 04:49:48
• 言語: C++17 (gcc 13.3.0 + boost 1.87.0)
• 結果: AC
• 実行時間: 339 ms / 3,000 ms
• コード長: 13,753 bytes
• コンパイル時間: 2,836 ms
• コンパイル使用メモリ: 236,548 KB
• 実行使用メモリ: 25,192 KB
• 最終ジャッジ日時: 2025-07-19 04:50:01
• 合計ジャッジ時間: 13,193 ms
• ジャッジサーバーID （参考情報）: judge1 / judge3

ファイルパターン	結果
sample	AC * 2
other	AC * 38

ソースコード

#include <bits/stdc++.h>
using namespace std;

template<int idx>
struct Montgomery{
    //2^62未満&奇数modのみ.
    //初めにsetmodする.
    using u64 = uint64_t;
    using u128 = __uint128_t;
 
    private:
    static u64 mod,N2,Rsq; //N*N2≡1(mod N);
    //Rsq = R^2modN; R=2^64.
    u64 v = 0;
    public:
    long long val()const{return reduce(v);}
    static constexpr u64 getmod(){return mod;}
    static void setmod(u64 m){
        assert(m<(1LL<<62)&&(m&1));
        mod = m; N2 = mod;
        for(int i=0; i<5; i++) N2 *= 2-N2*mod;
        Rsq = (-u128(mod))%mod;
    }
    //reduce = T*R^-1modNを求める.
    u64 reduce(const u128 &T)const{
        //T*R^-1≡(T+(T*(-N2))modR*N)/R 2N未満なので-N必要かだけで良い.
        u64 ret = (T+u128(((u64)T)*(-N2))*mod)>>64;
        if(ret >= mod) ret -= mod;
        return ret;
    }
    //初期値<mod. 初めにw*R modN...->reduce(R^2)でok.
    Montgomery(){v = 0;} Montgomery(long long w):v(reduce(u128(w)*Rsq)){}
 
    Montgomery& operator=(const Montgomery &b) = default;
    Montgomery operator-()const{return Montgomery()-Montgomery(*this);}
    Montgomery operator+(const Montgomery &b)const{return Montgomery(*this)+=b;}
    Montgomery operator-(const Montgomery &b)const{return Montgomery(*this)-=b;}
    Montgomery operator*(const Montgomery &b)const{return Montgomery(*this)*=b;}
    Montgomery operator/(const Montgomery &b)const{return Montgomery(*this)/=b;}
    Montgomery& operator+=(const Montgomery &b){
        v += b.v;
        if(v >= mod) v -= mod;
        return (*this);
    }
    Montgomery& operator-=(const Montgomery &b){
        v += mod-b.v;
        if(v >= mod) v -= mod;
        return (*this);
    }
    Montgomery& operator*=(const Montgomery &b){
        v = reduce(u128(v)*b.v);
        return (*this);
    }
    Montgomery& operator/=(const Montgomery &b){
        (*this) *= b.inv();
        return (*this);
    }
    Montgomery pow(u64 b)const{
        Montgomery ret = 1,p = (*this);
        if(b < 0) p = p.inv(),b = -b;
        while(b){
            if(b&1) ret *= p;
            p *= p; b >>= 1;
        }
        return ret;
    }
    Montgomery inv()const{return pow(mod-2);}
 
    bool operator!=(const Montgomery &b)const{return v!=b.v;}
    bool operator==(const Montgomery &b)const{return v==b.v;}
};
template<int idx> uint64_t Montgomery<idx>::mod;
template<int idx> uint64_t Montgomery<idx>::N2;
template<int idx> uint64_t Montgomery<idx>::Rsq;
using mont = Montgomery<0>;
 
bool MillerRabin(long long N,const vector<long long> &A){
    mont::setmod(N);
    long long s = __builtin_ctzll(N-1),d = N-1;
    d >>= s;
    for(auto &a : A){
        if(N <= a) break;
        mont x = mont(a).pow(d);
        if(x != 1){
            long long t;
            for(t=0; t<s; t++){
                if(x == N-1) break;
                x *= x;
            }
            if(t == s) return false;
        }
    }
    return true;
}
bool isprime(const long long N){
    if(N <= 1) return false;
    else if(N == 2) return true;
    else if(N%2 == 0) return false;
    else if(N < 4759123141LL) return MillerRabin(N,{2,7,61});
    else return MillerRabin(N, {2,325,9375,28178,450775,9780504,1795265022});
}
random_device rnd;
mt19937 mt(rnd());
mt19937_64 mt2(rnd());
int getprime1(int minv,int range){
    assert(minv+range >= 2);
    int ret = -1;
    while(true){
        ret = mt()%range+minv;
        if(isprime(ret)) return ret;
    }
}
long long getprime2(long long minv,long long range){
    assert(minv+range >= 2);
    long long ret = -1;
    while(true){
        ret = mt2()%range+minv;
        if(isprime(ret)) return ret;
    }
}

//入力が必ず-mod<a<modの時.
template<int idx> //modが入力で与えられる場合. 
struct dynamic_modint{ //mod変更が可能 最初にsetmod必須 idxで複数個所持が可能.
    private:
    static int mod;
    public:
    long long v = 0;
    static constexpr long long getmod(){return mod;}
    static void setmod(int m){
        assert(m > 0);
        mod = m;
    }
    dynamic_modint(){v = 0;}
    dynamic_modint(int a){v = a<0?a+mod:a;} dynamic_modint(long long a){v = a<0?a+mod:a;}
    dynamic_modint(unsigned int a){v = a;}
    dynamic_modint(unsigned long long a){v = a;}
    long long val()const{return v;}
 
    dynamic_modint &operator=(const dynamic_modint &b) = default;
    dynamic_modint operator+()const{return (*this);}
    dynamic_modint operator-()const{return dynamic_modint(0)-(*this);}
    dynamic_modint operator+(const dynamic_modint b)const{return dynamic_modint(v)+=b;}
    dynamic_modint operator-(const dynamic_modint b)const{return dynamic_modint(v)-=b;}
    dynamic_modint operator*(const dynamic_modint b)const{return dynamic_modint(v)*=b;}
    dynamic_modint operator/(const dynamic_modint b)const{return dynamic_modint(v)/=b;}
    dynamic_modint operator+=(const dynamic_modint b){
        v += b.v; if(v >= mod) v -= mod;
        return *this;
    }
    dynamic_modint operator-=(const dynamic_modint b){
        v -= b.v; if(v < 0) v += mod; 
        return *this;
    }   
    dynamic_modint operator*=(const dynamic_modint b){v = v*b.v%mod; return *this;}
    dynamic_modint operator/=(dynamic_modint b){ //b!=0 mod素数が必須.
        if(b == 0) assert(false);
        int left = mod-2;
        while(left){if(left&1) *this *= b; b *= b; left >>= 1;}
        return *this;
    }
    dynamic_modint operator++(){*this += 1; return *this;}
    dynamic_modint operator--(){*this -= 1; return *this;}
    dynamic_modint operator++(int){*this += 1; return *this;}
    dynamic_modint operator--(int){*this -= 1; return *this;}
    bool operator==(const dynamic_modint b)const{return v == b.v;}
    bool operator!=(const dynamic_modint b)const{return v != b.v;}
    bool operator>(const dynamic_modint b)const{return v > b.v;}
    bool operator>=(const dynamic_modint b)const{return v >= b.v;}
    bool operator<(const dynamic_modint b)const{return v < b.v;}
    bool operator<=(const dynamic_modint b)const{return v <= b.v;}
    dynamic_modint pow(long long n)const{
        dynamic_modint ret = 1,p = v;
        if(n < 0) p = p.inv(),n = -n;
        while(n){
            if(n&1) ret *= p;
            p *= p; n >>= 1;
        }
        return ret;
    }
    dynamic_modint inv()const{return dynamic_modint(1)/v;} //素数mod必須.
};
template<int idx> int dynamic_modint<idx>::mod=998244353;
using mint = dynamic_modint<0>;

using SS = mint;
mint zero = 0;
class SegmentTree{
    public:
    int siz = -1,n = -1;
    vector<SS> dat;
 
    SS op(SS a, SS b){return a+b;}
    SS e(){return zero;}
    void renew (SS &a,SS x){
        a = op(a,x);
        //a = x; //set(pos,x)で可能.
        //その他.
    }
 
    SegmentTree(int N){init(N);}
    SegmentTree(const vector<SS> &A){//長さ配列サイズに合わせる.
        siz = 1; n = A.size();
        while(siz < n) siz *= 2;
        dat.resize(siz*2,e());
        for(int i=0; i<n; i++) dat.at(i+siz) = A.at(i);
        for(int i=siz-1; i>0; i--) dat.at(i) = op(dat.at(i*2),dat.at(i*2+1));
    }
    void init(int N){
        //全要素単位元に初期化.
        siz = 1; n = N;
        while(siz < n) siz *= 2;
        dat.assign(siz*2,e());
    }
    void init(const vector<SS> &A){//長さ配列サイズに合わせる.
        siz = 1; n = A.size();
        while(siz < n) siz *= 2;
        dat.resize(siz*2,e());
        for(int i=0; i<n; i++) dat.at(i+siz) = A.at(i);
        for(int i=siz-1; i>0; i--) dat.at(i) = op(dat.at(i*2),dat.at(i*2+1));
    }
    void set(int pos,SS x){
        pos = pos+siz;
        dat.at(pos) = x;
        while(pos != 1){
            pos = pos/2;
            dat.at(pos) = op(dat.at(pos*2),dat.at(pos*2+1));
        }
    }
    void update(int pos,SS x){
        pos = pos+siz;
        renew(dat.at(pos),x);
        while(pos != 1){
            pos = pos/2;
            dat.at(pos) = op(dat.at(pos*2),dat.at(pos*2+1));
        }
    } 
    SS findans(int l, int r){
        SS retl = e(),retr = e();
        l += siz,r += siz;
        while(l < r){
            if(l&1) retl = op(retl,dat.at(l++));
            if(r&1) retr = op(dat.at(--r),retr);
            l >>= 1; r >>= 1;
        }
        return op(retl,retr);
    }
    SS get(int pos){return dat.at(pos+siz);}
    SS rangeans(int l, int r){return findans(l,r);}
    SS allrange(){return dat.at(1);}
 
    //rightは) leftは[で 渡す&返す. 
    int maxright(const function<bool(SS)> f,int l = 0){
        //fを満たさない最小の箇所を返す なければn.
        l += siz; int r = n+siz;
        vector<int> ls,rs;
        while(l < r){
            if(l&1) ls.push_back(l++);
            if(r&1) rs.push_back(--r);
            l >>= 1; r >>= 1; 
        }
        SS okl = e();
        for(int i=0; i<ls.size(); i++){
            l = ls.at(i);
            SS now = op(okl,dat.at(l));
            if(!f(now)){
                while(l < siz){
                    l <<= 1;
                    now = op(okl,dat.at(l));
                    if(f(now)){okl = now; l++;}
                }
                return l-siz;
            } 
            okl = now;
        }
        for(int i=rs.size()-1; i>=0; i--){
            l = rs.at(i);
            SS now = op(okl,dat.at(l));
            if(!f(now)){
                while(l < siz){
                    l <<= 1;
                    now = op(okl,dat.at(l));
                    if(f(now)){okl = now; l++;}
                }
                return l-siz;
            } 
            okl = now;
        }
        return n;
    }
    int minleft(const function<bool(SS)> f,int r = -1){
        //fを満たす最小の箇所を返す なければ0.
        if(r == -1) r = n;
        int l = siz; r += siz;
        vector<int> ls,rs;
        while(l < r){
            if(l&1) ls.push_back(l++);
            if(r&1) rs.push_back(--r);
            l >>= 1; r >>= 1; 
        }
        SS okr = e();
        for(int i=0; i<rs.size(); i++){
            r = rs.at(i);
            SS now = op(dat.at(r),okr);
            if(!f(now)){
                while(r < siz){
                    r <<= 1; r++;
                    now = op(dat.at(r),okr);
                    if(f(now)){okr = now; r--;}
                }
                return r+1-siz;
            }
            okr = now;
        }
        for(int i=ls.size()-1; i>=0; i--){
            r = ls.at(i);
            SS now = op(dat.at(r),okr);
            if(!f(now)){
                while(r < siz){
                    r <<= 1; r++;
                    now = op(dat.at(r),okr);
                    if(f(now)){okr = now; r--;}
                }
                return r+1-siz;
            }
            okr = now;
        }
        return 0;
    }
};

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int H,W,N; cin >> H >> W >> N;
    long long mod = getprime2(1LL<<30,1LL<<30);
    mint::setmod(mod);

    mint B1 = getprime1(100100100,100100100);
    mint B2 = getprime1(200200200,100100100);
    vector<mint> pb1(H,1),pb2(W,1),invpb1(H,1),invpb2(W,1);
    for(int i=1; i<H; i++) pb1.at(i) = pb1.at(i-1)*B1;
    for(int i=1; i<W; i++) pb2.at(i) = pb2.at(i-1)*B2;
    B1 = B1.inv(),B2 = B2.inv();
    for(int i=1; i<H; i++) invpb1.at(i) = invpb1.at(i-1)*B1;
    for(int i=1; i<W; i++) invpb2.at(i) = invpb2.at(i-1)*B2;

    vector<tuple<int,int,int>> XY; XY.reserve(N);
    while(N--){
        int x,y,v; cin >> x >> y >> v;
        if(v == 0) continue;
        x--; y--;
        XY.push_back({x,y,v});
    }
    sort(XY.begin(),XY.end());
    int Q; cin >> Q;
    vector<tuple<int,int,bool,int>> Qs,Qt; Qs.reserve(4*Q),Qt.reserve(4*Q);
    vector<mint> S(Q),T(Q),mulS(Q),mulT(Q);
    for(int i=0; i<Q; i++){
        int d,l,u,r; cin >> d >> l >> u >> r; d--,l--,u--,r--;
        if(d && l) Qs.push_back({d-1,l-1,true,i});
        if(d) Qs.push_back({d-1,r,false,i});
        if(l) Qs.push_back({u,l-1,false,i});
        Qs.push_back({u,r,true,i});   
        if(u+1 != H && r+1 != W) Qt.push_back({u+1,r+1,true,i});
        if(u+1 != H) Qt.push_back({u+1,l,false,i});
        if(r+1 != W) Qt.push_back({d,r+1,false,i});
        Qt.push_back({d,l,true,i});
        mulS.at(i) = invpb1.at(d)*invpb2.at(l);
        mulT.at(i) = invpb1.at(H-1-u)*invpb2.at(W-1-r);

    }
    sort(Qs.begin(),Qs.end());
    sort(Qt.rbegin(),Qt.rend());

    vector<mint> V(10);
    for(int i=0; i<10; i++) V.at(i) = i;

    SegmentTree Z(W);
    int pos = 0;
    for(auto [x,y,w] : XY){
        while(pos < Qs.size()){
            auto [x2,y2,plus,qpos] = Qs.at(pos);
            if(x <= x2) break;
            if(plus) S.at(qpos) += Z.rangeans(0,y2+1);
            else S.at(qpos) -= Z.rangeans(0,y2+1);
            pos++;
        }
        Z.update(y,V.at(w)*pb1.at(x)*pb2.at(y));
    }
    while(pos < Qs.size()){
        auto [x2,y2,plus,qpos] = Qs.at(pos);
        if(plus) S.at(qpos) += Z.rangeans(0,y2+1);
        else S.at(qpos) -= Z.rangeans(0,y2+1);
        pos++;
    }
    pos = 0; Z.init(W);
    reverse(XY.begin(),XY.end());
    for(auto [x,y,w] : XY){
        if(w == 6) w = 9;
        else if(w == 9) w = 6;
        while(pos < Qt.size()){
            auto [x2,y2,plus,qpos] = Qt.at(pos);
            if(x >= x2) break;
            if(plus) T.at(qpos) += Z.rangeans(y2,W);
            else T.at(qpos) -= Z.rangeans(y2,W);
            pos++;
        }
        Z.update(y,V.at(w)*pb1.at(H-1-x)*pb2.at(W-1-y));
    }
    
    while(pos < Qt.size()){
        auto [x2,y2,plus,qpos] = Qt.at(pos);
        if(plus) T.at(qpos) += Z.rangeans(y2,W);
        else T.at(qpos) -= Z.rangeans(y2,W);
        pos++;
    }

    for(int i=0; i<Q; i++){
        if(S.at(i)*mulS.at(i) == T.at(i)*mulT.at(i)) cout << "Yes\n";
        else cout << "No\n";
    }
}