結果

問題 No.1891 Static Xor Range Composite Query
ユーザー 37zigen37zigen
提出日時 2022-04-04 20:59:40
言語 Java21
(openjdk 21)
結果
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
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 221 ms
100,736 KB
testcase_01 AC 266 ms
106,440 KB
testcase_02 AC 253 ms
106,396 KB
testcase_03 AC 252 ms
106,752 KB
testcase_04 AC 248 ms
106,584 KB
testcase_05 AC 252 ms
106,580 KB
testcase_06 AC 253 ms
106,616 KB
testcase_07 AC 275 ms
106,680 KB
testcase_08 AC 249 ms
106,576 KB
testcase_09 AC 246 ms
104,860 KB
testcase_10 AC 256 ms
106,924 KB
testcase_11 AC 310 ms
108,588 KB
testcase_12 AC 304 ms
108,552 KB
testcase_13 AC 307 ms
108,956 KB
testcase_14 AC 303 ms
108,696 KB
testcase_15 AC 310 ms
108,568 KB
testcase_16 AC 342 ms
108,872 KB
testcase_17 AC 305 ms
108,636 KB
testcase_18 AC 304 ms
108,704 KB
testcase_19 AC 323 ms
108,568 KB
testcase_20 AC 312 ms
108,676 KB
testcase_21 AC 1,520 ms
140,068 KB
testcase_22 AC 1,426 ms
139,736 KB
testcase_23 AC 1,627 ms
139,832 KB
testcase_24 AC 1,505 ms
139,708 KB
testcase_25 AC 1,495 ms
139,856 KB
testcase_26 AC 1,455 ms
139,684 KB
testcase_27 AC 1,469 ms
139,824 KB
testcase_28 AC 1,515 ms
139,740 KB
testcase_29 AC 1,532 ms
140,060 KB
testcase_30 AC 1,462 ms
139,776 KB
権限があれば一括ダウンロードができます

ソースコード

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();
    }
}
0