网站建设 模板网站,怎样做电商 入手,网站开发概要设计,北海seo快速排名CF1580C Train Maintenancedescriptionsolutioncodedescription
题目链接
solution
这是一种利用根号平衡时间复杂度的套路
分α\alphaα【操作参数】与n\sqrt{n}n的关系#xff0c;一半采取暴力#xff0c;一半利用工具特殊处理 对于本题#xff0c;假设第iii辆车的加…
CF1580C Train Maintenancedescriptionsolutioncodedescription
题目链接
solution
这是一种利用根号平衡时间复杂度的套路
分α\alphaα【操作参数】与n\sqrt{n}n的关系一半采取暴力一半利用工具特殊处理 对于本题假设第iii辆车的加入时间为tit_iti那么在nownownow时刻第iii辆车在维修的条件为(now−ti)%(xiyi)≥xi(now-t_i)\%(x_iy_i)\ge x_i(now−ti)%(xiyi)≥xi 当xiyi≥mx_iy_i\ge\sqrt{m}xiyi≥m的时候 “工作维修”的周期不会超过m\sqrt{m}m可以差分在每个周期上暴力修改 当xiyimx_iy_i\sqrt{m}xiyim的时候 实时维护一个gi,jg_{i,j}gi,j数组表示第t≡j(modi)t\equiv j\pmod it≡j(modi)天时有gi,jg_{i,j}gi,j辆xyixyixyi的车正在维修 对于加入/丢掉的火车将gi,(xtk)mod i±1g_{i,(xt_k)\text{mod}\ i}±1gi,(xtk)mod i±1 直接查询∑gi,nowmod i\sum g_{i,now\ \text{mod}\ i}∑gi,now mod i
code
#include cmath
#include cstdio
#include iostream
using namespace std;
#define maxn 200005
#define maxB 1000
int n, m;
int x[maxn], y[maxn], t[maxn], f[maxn];
int g[maxB][maxB];void modify( int i, int j ) {if( i m ) return;else f[i] j;
}int main() {scanf( %d %d, n, m );int sqt sqrt( m );for( int i 1;i n;i ) scanf( %d %d, x[i], y[i] );for( int i 1, op, k, lst 0;i m;i ) {scanf( %d %d, op, k );int v op 1 ? 1 : -1;if( op 1 ) t[k] i;if( x[k] y[k] sqt ) {for( int j t[k] x[k];j m;j x[k] y[k] )modify( max( j, i ), v ), modify( max( j y[k], i ), -v );}else {for( int j t[k] x[k];j t[k] x[k] y[k];j )g[x[k] y[k]][j % ( x[k] y[k] )] v;}int ans lst f[i];lst ans; //差分数组的辅助for( int j 1;j sqt;j ) ans g[j][i % j];printf( %d\n, ans );}return 0;
}
