結果

問題 No.1891 Static Xor Range Composite Query
ユーザー 37zigen
提出日時 2022-04-04 20:59:40
言語 Java
(openjdk 23)
結果
AC  
実行時間 1,627 ms / 5,000 ms
コード長 5,299 bytes
コンパイル時間 2,850 ms
コンパイル使用メモリ 80,540 KB
実行使用メモリ 140,068 KB
最終ジャッジ日時 2024-11-25 14:19:35
合計ジャッジ時間 27,083 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 30
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.NoSuchElementException;
public class Main implements Runnable { //Runnableを実装する
    public static void main(String[] args) {
        new Thread(null, new Main(), "", Runtime.getRuntime().maxMemory()).start(); //16MBスタックを確保して実行
    }
    public void run() {
        solve();
    }
    
    final long mod=998244353;
    
    class Query implements Comparable<Query> {
        int l;
        int r;
        int p;
        long x;
        int id;
        
        public Query(int l, int r, int p, long x, int id) {
            this.l=l;
            this.r=r;
            this.p=p;
            this.x=x;
            this.id=id;
        }
        
        int reverseOrder() {
            int b=0;
            for (int i=17;i>=0;--i) {
                b|=((p>>i)%2)<<(17-i);
            }
            return b;
        }
        
        @Override
        public int compareTo(Main.Query o) {
            return Integer.compare(reverseOrder(), o.reverseOrder());
        }
    }
    
    class SegTree {
        long[][] f;
        int[] l_pointer;
        int[] r_pointer;
        
        int n=1<<18;
        public SegTree(int n_, long[] a_, long[] b_) {
            f=new long[2*n-1][2];
            l_pointer=new int[2*n-1];
            r_pointer=new int[2*n-1];
            for (int i=0;i<n;++i) f[i+n-1][0]=1;
            for (int i=0;i<n_;++i) {
                f[i+n-1][0]=a_[i];
                f[i+n-1][1]=b_[i];
            }
            for (int i=0;i<2*n-1;++i) {
                l_pointer[i]=2*i+1;
                r_pointer[i]=2*i+2;
            }
            for (int i=n-2;i>=0;--i) {
                f[i]=merge(f[l_pointer[i]], f[r_pointer[i]]);
            }
        }
        
        long[] merge(long[] fl, long[] fr) {
            return new long[] {fl[0]*fr[0]%mod, (fr[0]*fl[1]+fr[1])%mod};
        }
        
        long[] query(int l, int r, int L, int R, int k) {
            if (r <= L || R <= l) return new long[] {1, 0};
            if (L <= l && r <= R) return f[k];
            long[] vl=query(l, (l+r)/2, L, R, l_pointer[k]);
            long[] vr=query((l+r)/2, r, L, R, r_pointer[k]);
            return merge(vl, vr);
        }
        
        // 0-indexed
        // 下から bit 目
        void swap(int bit) {
            bit=17-bit;
            for (int i=0;i<(1<<bit);++i) {
                int k=(1<<bit)-1+i;
                l_pointer[k]^=r_pointer[k];r_pointer[k]^=l_pointer[k];l_pointer[k]^=r_pointer[k];
            }
            for (int i=(1<<(bit+1))-2;i>=0;--i) {
                f[i]=merge(f[l_pointer[i]], f[r_pointer[i]]);
            }
        }   
        
        long eval(int L, int R, long x) {
            long[] ab=query(0, n, L, R, 0);
            return (ab[0]*x+ab[1])%mod;
        }
    }
    
    public void solve() {
        FastScanner sc=new FastScanner();
        PrintWriter pw=new PrintWriter(System.out);
        
        int N=sc.nextInt();
        int Q=sc.nextInt();
        
        long[] A=new long[N];
        long[] B=new long[N];
        for (int i=0;i<N;++i) {
            A[i]=sc.nextLong();
            B[i]=sc.nextLong();
        }
        
        
        SegTree tree=new SegTree(N, A, B);
        
        int mask=0;
        
        ArrayList<Query> list=new ArrayList<>();
        for (int i=0;i<Q;++i) {
            int l=sc.nextInt();
            int r=sc.nextInt();
            int p=sc.nextInt();
            long x=sc.nextLong();
            list.add(new Query(l, r, p, x, i));
        }
        Collections.sort(list);
        long[] ans=new long[Q];
        for (int i=0;i<Q;++i) {
            Query query=list.get(i);
            int xor=mask^query.p;
            for (int shift=0;shift<18;++shift) {
                if ((xor>>shift)%2==1) {
                    tree.swap(shift);
                    mask^=1<<shift;
                }
            }
            ans[query.id]=tree.eval(query.l, query.r, query.x);
        }
        for (int i=0;i<Q;++i) {
            pw.println(ans[i]);
        }
        pw.close();
    }
    static void tr(Object...objects) {
        System.out.println(Arrays.deepToString(objects));
    }
    
}
class FastScanner {
    private final InputStream in = System.in;
    private final byte[] buffer = new byte[1024];
    private int ptr = 0;
    private int buflen = 0;
    private boolean hasNextByte() {
        if (ptr < buflen) {
            return true;
        }else{
            ptr = 0;
            try {
                buflen = in.read(buffer);
            } catch (IOException e) {
                e.printStackTrace();
            }
            if (buflen <= 0) {
                return false;
            }
        }
        return true;
    }
    private int readByte() { if (hasNextByte()) return buffer[ptr++]; else return -1;}
    private static boolean isPrintableChar(int c) { return 33 <= c && c <= 126;}
    private void skipUnprintable() { while(hasNextByte() && !isPrintableChar(buffer[ptr])) ptr++;}
    public boolean hasNext() { skipUnprintable(); return hasNextByte();}
    public String next() {
        if (!hasNext()) throw new NoSuchElementException();
        StringBuilder sb = new StringBuilder();
        int b = readByte();
        while(isPrintableChar(b)) {
            sb.appendCodePoint(b);
            b = readByte();
        }
        return sb.toString();
    }
    public long nextLong() {
        if (!hasNext()) throw new NoSuchElementException();
        long n = 0;
        boolean minus = false;
        int b = readByte();
        if (b == '-') {
            minus = true;
            b = readByte();
        }
        if (b < '0' || '9' < b) {
            throw new NumberFormatException();
        }
        while(true){
            if ('0' <= b && b <= '9') {
                n *= 10;
                n += b - '0';
            }else if(b == -1 || !isPrintableChar(b)){
                return minus ? -n : n;
            }else{
                throw new NumberFormatException();
            }
            b = readByte();
        }
    }
    public int nextInt() {
        return (int)nextLong();
    }
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0