結果

問題 No.1891 Static Xor Range Composite Query
ユーザー 37zigen
提出日時 2022-04-04 20:44:43
言語 Java
(openjdk 23)
結果
AC  
実行時間 1,364 ms / 5,000 ms
コード長 5,420 bytes
コンパイル時間 2,130 ms
コンパイル使用メモリ 80,424 KB
実行使用メモリ 98,112 KB
最終ジャッジ日時 2024-11-25 13:55:02
合計ジャッジ時間 21,617 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
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[] a;
		long[] b;
		int[] l_pointer;
		int[] r_pointer;
		
		int n=1<<18;

		public SegTree(int n_, long[] a_, long[] b_) {
			a=new long[2*n-1];
			b=new long[2*n-1];
			l_pointer=new int[2*n-1];
			r_pointer=new int[2*n-1];
			Arrays.fill(a, 1);
			for (int i=0;i<n_;++i) {
				a[i+n-1]=a_[i];
				b[i+n-1]=b_[i];
			}
			for (int i=n-2;i>=0;--i) {
				long[] ab=merge(a[2*i+1], b[2*i+1], a[2*i+2], b[2*i+2]);
				a[i]=ab[0];
				b[i]=ab[1];
				l_pointer[i]=2*i+1;
				r_pointer[i]=2*i+2;
			}
		}
		
		long[] merge(long al, long bl, long ar, long br) {
			return new long[] {ar*al%mod, (ar*bl+br)%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 new long[] {a[k], b[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[0], vl[1], vr[0], vr[1]);
		}
		
		// 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) {
				long[] ab=merge(a[l_pointer[i]], b[l_pointer[i]], a[r_pointer[i]], b[r_pointer[i]]);
				a[i]=ab[0];
				b[i]=ab[1];
			}
		}	
		
		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();
    }
}
0