Problem Solution——[TJOI2018] Mathematical Calculation
I really didn’t see that this is a line segment tree
topic surface transportation
Xiaodou now has a number x, the initial value is 1. Xiaodou has Q operations, operations are Two types:
1 m: x = x * m, output x%mod;
2 pos: x = x / the number multiplied by the pos operation (guarantee pos operations must be type 1, and each type 1 operation will be divided at most once), output x%mod
There are a total of t groups of inputs (t ≤ 5)
For each group of input, the first line is two numbers Q, mod(Q ≤ 100000, mod ≤ 1000000000);
Next Q lines, each line of operation type op, the operation number or the number m multiplied by (to ensure that all inputs are legal).
1 ≤ Q ≤ 100000
For each operation, output one line, including the operation The value of x%mod after execution
idea
We can use a line segment tree to maintain the time axis, and the initial value is all 1. , Operation 1 changes the point to m, and operation 2 changes it back to 1. It’s a big problem, but it’s wonderful.
#includeusing namespace std ;const int MAXN = 100005 ;#define ll long longinline ll read(){ ll s=0; char g=getchar (); while(g>'9'||g<'0')g=getchar(); while(g>='0'&&g<='9')s=s*10+g-'0' ,g=getchar(); return s ;}ll T, Q, mod ;struct Seg{ int l, r; ll sum; }t[ MAXN<<2 ]; void build( int p, int l, int r) {//Without updata, all are 1 t[ p ].l = l, t[ p ].r = r, t[ p ].sum = 1; if( l == r )return; int mid = (l +r )>>1; build( p<<1, l, mid), build( p<<1|1, mid+1 ,r) ;}void change( int p, int loc, ll val ){ if (t[ p ].l == t[ p ].r ){ t[ p ].sum = val; return;} int mid = (t[ p ].l + t[ p ].r )>>1 ; if( loc <= mid )change( p<<1, loc, val); else change( p<<1|1, loc, val); t[ p ].sum = (t[ p<<1] .sum*t[ p<<1|1 ].sum )%mod; }void delelt( int p, int loc ){ if( t[ p ].l == t[ p ].r ){ t[ p ].sum = 1; return;} int mid = (t[ p ].l + t[ p ].r )>>1; if( loc <= mid )delelt( p<<1, loc); else delelt( p<<1|1, loc); t[ p ].sum = (t[ p<<1 ].sum*t[ p<<1|1 ].sum )%mod; }int main( ){ T = read(); while( T-- ){ Q = read(), mod = read(); ll m1, m2; build( 1, 1, Q); for( int i = 1; i < = Q; ++i ){ m1 = read(), m2 = read(); if( m1 == 1) change( 1, i, m2); else delelt( 1, m2); printf("%lld\ n", t[ 1 ].sum);}} return 0 ;}