生活随笔
收集整理的這篇文章主要介紹了
codeforces438 D. The Child and Sequence
小編覺得挺不錯的,現(xiàn)在分享給大家,幫大家做個參考.
2020威海區(qū)域賽G. Caesar Cipher就用到了此思想（
今天碰到模板題了還是再寫一遍吧
D. The Child and Sequence
區(qū)間取模操作模板題
有一個公式 x%p<x2(x>p)x\%p<\frac{x}{2}(x>p)x%p<2x?(x>p) 由此對于每一個數(shù)最多模log次，如果我們保留修改每個數(shù)的值最多修改mlog(ai)mlog(a_i)mlog(ai?)次，記錄區(qū)間最值并判斷是否遞歸（剪紙）。
時間復雜度nlognlogainlognloga_inlognlogai?
#define IO ios::sync_with_stdio(false);cin.tie();cout.tie(0)
#pragma GCC optimize(2)
#include<set>
#include<map>
#include<cmath>
#include<stack>
#include<queue>
#include<random>
#include<bitset>
#include<string>
#include<vector>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<unordered_map>
#include<unordered_set>
using namespace std
;
typedef long long ll
;
typedef pair
<int,int> pii
;
const int mod
=998244353;
const int N
=100010;
struct node
{int l
,r
;ll sum
,mx
;
}tree
[N
<<2];
int n
,m
;
ll a
[N
];
void pushup(int u
)
{tree
[u
].mx
=max(tree
[u
<<1].mx
,tree
[u
<<1|1].mx
);tree
[u
].sum
=tree
[u
<<1].sum
+tree
[u
<<1|1].sum
;
}
void build(int u
,int l
,int r
)
{tree
[u
]={l
,r
};if(l
==r
) {tree
[u
].sum
=tree
[u
].mx
=a
[l
];return;}int mid
=l
+r
>>1;build(u
<<1,l
,mid
);build(u
<<1|1,mid
+1,r
);pushup(u
);
}
void modify1(int u
,int l
,int r
,ll mod
)
{if(tree
[u
].mx
<mod
) return;if(tree
[u
].l
==tree
[u
].r
) {tree
[u
].sum
%=mod
;tree
[u
].mx
%=mod
;return;}int mid
=tree
[u
].l
+tree
[u
].r
>>1;if(l
<=mid
) modify1(u
<<1,l
,r
,mod
);if(r
>mid
) modify1(u
<<1|1,l
,r
,mod
);pushup(u
);
}
void modify2(int u
,int pos
,ll v
)
{if(tree
[u
].l
==tree
[u
].r
) {tree
[u
].mx
=tree
[u
].sum
=v
;return;}int mid
=tree
[u
].l
+tree
[u
].r
>>1;if(pos
<=mid
) modify2(u
<<1,pos
,v
);else modify2(u
<<1|1,pos
,v
);pushup(u
);
}
ll
query(int u
,int l
,int r
)
{if(tree
[u
].l
>=l
&&tree
[u
].r
<=r
) return tree
[u
].sum
;ll v
=0;int mid
=tree
[u
].l
+tree
[u
].r
>>1;if(l
<=mid
) v
+=query(u
<<1,l
,r
);if(r
>mid
) v
+=query(u
<<1|1,l
,r
);return v
;
}
int main()
{int T
=1;while(T
--){cin
>>n
>>m
;for(int i
=1;i
<=n
;i
++) cin
>>a
[i
];build(1,1,n
);while(m
--){int op
,l
,r
;cin
>>op
>>l
>>r
;if(op
==1)cout
<<query(1,l
,r
)<<'\n';else if(op
==2){ll x
;cin
>>x
;modify1(1,l
,r
,x
);}elsemodify2(1,l
,r
);}}return 0;
}
區(qū)間開根號，區(qū)間取模，都是不滿足區(qū)間性質(zhì)但是由于總操作次數(shù)比較少可以暴力修改。
總結
以上是生活随笔為你收集整理的codeforces438 D. The Child and Sequence的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。
