可能な限り簡潔にします。
CF679E
直接代入と修正のタイミングが正しいことがわかりますので、書き方について説明します。区間を良い数に変える操作を「加算」と呼びます。
既に区間代入が行われた区間にUpというマークを付けると、その区間とその子区間は1つの点と見なせます。そのため、修正の複雑さは単点修正と同じになります。
したがって、加算操作は次のように記述できます。
void applyAddition(int node, long long value){
if(tree[node].hasUpdate){
tree[node].difference -= value;
tree[node].minimum = tree[node].difference;
while(tree[node].difference < 0){
tree[node].difference += prime[tree[node].updateLevel + 1] - prime[tree[node].updateLevel];
tree[node].updateLevel++;
tree[node].minimum = tree[node].difference;
}
}
else{
tree[node].minimum -= value;
tree[node].lazy += value;
}
return;
}
完全なコード
UOJ515
時間順序で位置を維持することは難しいです。なぜなら、修正値に特別な性質がないからです。
問題の後缀という要件からアプローチします。
位置を後ろから前に向かって見ると、線分木のノードは現在の時刻の後缀最小値mxと、数量cntを維持します（例えば葉ノード1は1時刻の後缀最小値を表します）。
区間のmxが変化するとcntが増加することがわかります。したがって、無区間加算のセグメントツリーを使用して維持できます。
完全なコード
CF1588F
交換操作は、環を合成したり分解したりする可能性があるため、線分木での維持が難しくなります。そこで、根号複雑度の方法を検討します。
B個の操作ごとに1回処理を行うとします。
2番目と3番目の操作の点をキーポイントとし、1つのキーポイントから次のキーポイントまでの間のチェーンを1つのノードに圧縮すると、ノード数はBのオーダーになります。
2番目の操作の場合、1回はBのオーダーです。Bを√nに設定します。
完全なコード
CUTPLANT
切り取った後の花の高さをB、切り取る前の高さをAとします。Bの昇順で処理すると、同じBの間でmaxB≤BかつminA≥Bであれば、この切り取り操作をまとめて実行できます。
線分木で維持します。
#include<cstdio>
#include<iostream>
#include<algorithm>
#pragma GCC optimize(3,"inline","Ofast")
using namespace std;
const int INF=2e9;
const int MAXN=1e5+5;
typedef pair<int,int> Pair;
struct Person{
int height, id;
}people[MAXN];
int T, answer, n, heights[MAXN], segTreeMin[MAXN<<3], segTreeMax[MAXN<<3];
bool impossible;
bool compare(Person x, Person y){return x.height == y.height ? x.id < y.id : x.height < y.height;}
void updateNode(int node){segTreeMin[node] = min(segTreeMin[node<<1], segTreeMin[node<<1|1]); segTreeMax[node] = max(segTreeMax[node<<1], segTreeMax[node<<1|1]);}
void buildTree(int node, int left, int right){
if(left == right){segTreeMin[node] = heights[left]; segTreeMax[node] = people[left].height; return;}
int mid = (left + right) >> 1; buildTree(node<<1, left, mid); buildTree(node<<1|1, mid+1, right); updateNode(node);
}
Pair query(int node, int queryL, int queryR, int left, int right){
if(left > queryR || right < queryL) return Pair(INF, -INF);
else if(left >= queryL && right <= queryR){return Pair(segTreeMin[node], segTreeMax[node]);}
else{
Pair leftResult, rightResult; int mid = (left + right) >> 1;
leftResult = query(node<<1, queryL, queryR, left, mid); rightResult = query(node<<1|1, queryL, queryR, mid+1, right);
return Pair(min(leftResult.first, rightResult.first), max(leftResult.second, rightResult.second));
}
}
int main(){
scanf("%d",&T);
while(T--){
scanf("%d",&n); answer = 0; impossible = false;
for(int i=1;i<=n;i++) scanf("%d",&heights[i]);
for(int i=1;i<=n;i++){
scanf("%d",&people[i].height); people[i].id = i;
if(people[i].height > heights[i]){impossible = true;}
}
if(impossible){printf("-1\n"); continue;}
buildTree(1,1,n); sort(people+1, people+1+n, compare);
for(int i=1;i<=n;i++){
int j=i, B=people[i].height; int temp=0;
while(people[j+1].height == people[j].height){j++; if(j==n) break;}
for(int k=i;k<=j;k++){
if(temp == 0) temp = (heights[people[k].id] == people[k].height) ? 0 : 1;
else{
Pair result = query(1, people[k-1].id, people[k].id, 1, n);
if(result.first >= B && result.second <= B) continue;
else answer++, temp = (heights[people[k].id] == people[k].height) ? 0 : 1;
}
}
if(temp) answer++;
i=j;
}
printf("%d\n",answer);
}
return 0;
}
HDU6315
bが順列であり、毎回1ずつ増加する理由を考えます。区間のminbとmaxaを記録すると、maxa>minbのときに単点修正ができます。
#include<cstdio>
#include<cmath>
#include<iostream>
#include<algorithm>
using namespace std;
const int MAXN=1e5+5;
int n, m, values[MAXN];
void readInt(int &x){
x=0;
int sign=1;
char c=getchar();
while(c<'0'||c>'9'){
if(c=='-') sign=-1;
c=getchar();
}
while(c>='0'&&c<='9'){
x=(x<<3)+(x<<1)+(c^48);c=getchar();
}
x*=sign;
}
char operation[10];
struct SegmentTree{
struct Node{
int maxVal, sum, lazy, minB;
}nodes[MAXN<<2];
void updateNode(int node){
nodes[node].sum = nodes[node<<1].sum + nodes[node<<1|1].sum;
nodes[node].maxVal = max(nodes[node<<1].maxVal, nodes[node<<1|1].maxVal);
nodes[node].minB = min(nodes[node<<1].minB, nodes[node<<1|1].minB);
return;
}
void pushDown(int node){
if(!nodes[node].lazy) return;
nodes[node<<1].maxVal += nodes[node].lazy; nodes[node<<1|1].maxVal += nodes[node].lazy;
nodes[node<<1].lazy += nodes[node].lazy; nodes[node<<1|1].lazy += nodes[node].lazy; nodes[node].lazy = 0;
}
void build(int node, int left, int right){
nodes[node].sum = 0; nodes[node].maxVal = 0; nodes[node].lazy = 0;
if(left == right){
nodes[node].minB = values[left]; return;
}
int mid = left + right >> 1;
build(node<<1, left, mid); build(node<<1|1, mid+1, right); updateNode(node);
}
void update(int node, int queryL, int queryR, int left, int right){
if(left >= queryL && right <= queryR){
nodes[node].maxVal++;
if(nodes[node].maxVal < nodes[node].minB){
nodes[node].lazy++; return;
}
if(left == right && nodes[node].maxVal >= nodes[node].minB){
nodes[node].minB += values[left]; nodes[node].sum++; return;
}
}
pushDown(node);
int mid = left + right >> 1;
if(queryL <= mid) update(node<<1, queryL, queryR, left, mid);
if(queryR > mid) update(node<<1|1, queryL, queryR, mid+1, right);
updateNode(node);
}
int query(int node, int queryL, int queryR, int left, int right){
if(left >= queryL && right <= queryR){return nodes[node].sum;}
pushDown(node);
int mid = left + right >> 1, result = 0;
if(queryL <= mid) result += query(node<<1, queryL, queryR, left, mid);
if(queryR > mid) result += query(node<<1|1, queryL, queryR, mid+1, right);
return result;
}
}ST;
int main(){
while(~scanf("%d%d",&n,&m)){
for(int i=1;i<=n;i++) readInt(values[i]);
ST.build(1,1,n);
while(m--){
scanf("%s",operation+1);
if(operation[1]=='a'){
int l,r; readInt(l); readInt(r); ST.update(1,l,r,1,n);
}
else{
int l,r; readInt(l); readInt(r); printf("%d\n",ST.query(1,l,r,1,n));
}
}
}
return 0;
}
CF1458D
0,1を-1,1に置き換え、隣接する前缀和の値を辺で結びます。操作は環の辺を反転させることだとわかります。したがって、グラフを無向グラフと見なし、nowとnow-1の出辺数で方向を決定できます。
UOJ164
このような区間和の履歴最大値がない問題では、マーク(a,b)をx=max(x+a,b)と定義できます。
修正時にマークを結合し、maxを取ればよいです。
注意:マーク間には交換法則がありません！
完全なコード
CF1844G
HumanWisdom、dep[i]+dep[i+1]-2dep[lca(i,i+1)]=d[i]は直感的にわかります。
次に倍増法を考え、va[k]=2^kとします。dep[i]mod va[k]+dep[i+1]mod va[k]-2(dep[lca(i,i+1)]mod va[k-1])=d[i]mod va[k]
dep[1]=0であることがわかっているので、下から上に順推論できます。解なしの判定は簡単です。
完全なコード
NOI2015 寿司晩餐
8個の√500未満の素数しかありません。状態圧縮を考え、dp[i][s1][s2]を前i個の数まで、第1人が選んだ集合がs1、第2人が選んだ集合がs2であるとします。
iの素因数集合をsとすると、
dp[i][s1|s][s2] += dp[i][s1][s2], (s&s2==0)
dp[i][s1][s2|s] += dp[i][s1][s2], (s&s1==0)
1-nの数には√500より大きい素因子が1つしかありません。この因数をMAXと呼びます。
MAXが同じ数を一緒にして、これらの数は片方に属するか（または選ばれない）しかありません。
したがって、dpをf1,f2に分けて処理できます。
これらの数がすべて選ばれない場合があることに注意してください。このときのdpはこの状況を表します。したがって、dp=f1+f2-dp
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define ll long long
const int MAXN=500;
const int MAXM=256;
int n, Mod, f2[MAXM+5][MAXM+5], primes[10]={0,2,3,5,7,11,13,17,19,0};
ll Answer, dp[MAXM+5][MAXM+5], f1[MAXM+5][MAXM+5];
struct Person{int maxPrime, value; bool operator<(const Person &p)const{return maxPrime<p.maxPrime;};}persons[MAXN+5];
int main(){
scanf("%d%d",&n,&Mod);
for(int i=2;i<=n;i++){
int current=i; persons[i].maxPrime=-1;
for(int j=1;j<=8;j++){
if(current%primes[j]==0){
persons[i].value|=(1<<(j-1));
while(current%primes[j]==0){
current/=primes[j];
}
}
if(current!=1) persons[i].maxPrime=current;
}
}
sort(persons+2, persons+1+n);
dp[0][0]=1; persons[1].maxPrime=0;
for(int i=2;i<=n;i++){
if(i==2||persons[i].maxPrime!=persons[i-1].maxPrime||persons[i].maxPrime==-1){
for(int j=0;j<MAXM;j++){
for(int k=0;k<MAXM;k++){
f1[j][k]=dp[j][k]; f2[j][k]=dp[j][k];
}
}
}
for(int j=MAXM-1;j>=0;j--){
for(int k=MAXM-1;k>=0;k--){
if((j&k)!=0) continue;
if((persons[i].value&k)==0) f1[j|persons[i].value][k]=(f1[j][k]+f1[j|persons[i].value][k])%Mod;
if((persons[i].value&j)==0) f2[j][k|persons[i].value]=(f2[j][k|persons[i].value]+f2[j][k])%Mod;
}
}
if(i==n||persons[i].maxPrime!=persons[i+1].maxPrime||persons[i].maxPrime==-1){
for(int j=0;j<=MAXM;j++){
for(int k=0;k<MAXM;k++){
if((j&k)!=0) continue;
dp[j][k]=(((f1[j][k]+f2[j][k]-dp[j][k])%Mod)+Mod)%Mod;
}
}
}
}
for(int i=0;i<MAXM;i++){
for(int j=0;j<MAXM;j++){
if((i&j)==0) Answer=(Answer+dp[i][j])%Mod;
}
}
printf("%lld",Answer);return 0;
}
NOI2009 管道取珠
このa_i^2は、生成方法の数または各数量に対応する生成方法の数の計算が難しくなります。
意味を変換してみましょう。2つのパイプがあるとします。b_iをパイプ1,2がiシーケンスを得る方法数とすると、b_i=a_i^2となります。
すると簡単な伝票問題になります。
NOI2009 二分探索木
BSTには中順走査の一定の性質があります。dp[i][j][k]を中順走査が[i,j]のノードの値が>=kの方法数とします。
p∈[i,j]を根ノードとして取り出すと、[i,j]のノードの深さが+1になります。その貢献はアクセス頻度の和になります。
元の木では子ノードの値はすでにval[p]より大きいため、val[p]とkの大小関係を判断するだけでよいです。
NOI2014 購票
木分割と線分木に李超木を重ねる方法を簡単に考えられますが、時間複雑度は3つのlogです。
そこで、可撤回李超木を検討できます。これは可撤回併合-findセットと同様に、スタックで記録すればよいです。複雑度は2つのlogに低下しますが、メモリはまだ少し厳しいです。
[省選連考 2020 A 巻] 木
毎回部分木を実行するのは不可能なので、答えを子ノードに記録しようとします。
すべての値を+1してXOR和の結果を処理する必要があります。x=2^i-1 mod 2^iの場合、+1後にxの第iビットが反転することに注意します。
ビット操作を考え、va[i]=va[i]+dep[i]とし、現在の点をxとします。va[i]-dep[x]-1=2^j-1 mod 2^jであるiを見つける必要があります
簡略化するとva[i]=dep[x]の個数になります。
バケツで記録してからdsu on tree即可。
[省選連考 2021 A/B 巻] 滚榜
n≤13なので状態圧縮を考え、dp_{s,i,j,k}を現在の集合がs、最後の人がi、b[i]=j、使用したbの和がkとします。
この時間複雑度はOmicron(2^n n^2 m^2)です。
各発表順序について、bの具体的な割り当ては気にしません。
貪欲的に現在の人に、最小のコストで前の人を超えさせ、終了後に余分なbを後ろに積めばよいです。
dis_{i,j}をjがiを超える最小コストとすると、dis_{i,j}=max(0,a_i-a_j+(i