E. Replace the Numbers 1900 思维
https://codeforces.com/problemset/problem/1620/E
题解：正着做比较困难，我们可以考虑从后往前做。一个数会被变成什么样子是取决于其后的2操作。2操作可以等价为一个变换，而位置越后的2操作相较前面的2操作起着决定性作用，故从后往前遍历时前面的操作只能在已存在的变换上进行，比如u->v,只能将u->f(v)，而u不变是因为其时间轴上更靠前，所以它的优先级更高。故我们遍历即可得到答案。
另一种直观的理解可以把其按时间分为一个分部图，每一部分有n个点，当有变换时改变映射。
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=5e5+10;
struct node{
int u,v,w;
}a[N];
int f[N],b[N];
signed main(){
int n;cin>>n;
for(int i=1;i<=n;i++){
int k,x,y;cin>>k;
if(k==1){
cin>>x;
a[i]={1,x,0};
}
else{
cin>>x>>y;
a[i]={2,x,y};
}
}
for(int i=1;i<N;i++){
f[i]=i;
}
int t=0;
for(int i=n;i>=1;i--){
auto [u,v,w]=a[i];
if(u==1){
b[++t]=f[v];
}
else{
f[v]=f[w];
}
}
for(int i=t;i>=1;i--)
cout<<b[i]<<" ";
}
D. Infinite Set 1800
https://codeforces.com/contest/1635/problem/D
题解：4可以看作是二进制左移2位，2+1可以看作左移一位+1，我们可以对所有数从小到大排序，令二进制长度位p时的答案为f(p)（由于对于一个数x而言，其变换后的数必然互不相同，证明很显然），而x可以变成2x+1,4x两种形式，故f(p)=f(p+1)+f(p+2)+1,可以预处理。对于a[i]若其不能被其之前的数表示，则其所产生的所有数都没有出现过，否则a[i]一定可以被表示。而对于一个数x，其每次变换都至少*2,故可以logn判断其先前数是否出现过。最后加上所有答案即可，复杂度为O(nlogn).
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+10,mod=1e9+7;
map<int,int> v;
int a[N],f[N+100];
queue<int> q;
signed main(){
f[1]=2,f[0]=1;
for(int i=2;i<=N;i++){
f[i]=(f[i-1]+f[i-2]+1)%mod;
}
int n,p;cin>>n>>p;
for(int i=1;i<=n;i++) cin>>a[i];
sort(a+1,a+n+1);
int ans=0,res=0;
for(int i=1;i<=n;i++){
int cnt=0,x=a[i],ok=1;
while(x>0){
int now=0;
while(x%2&&x>0){
x=(x-1)/2;
if(v[x]) ok=0;
now=1;
}
while(x%4==0&&x>0){
x/=4;
if(v[x]){
ok=0;break;
}
now=1;
}
if(!ok) break;
if(!now) break;
}
if(!ok) continue;
v[a[i]]=1;
x=a[i];cnt=0;
while(x){
cnt++;x/=2;
}
if(cnt>p) continue;
ans=(ans+f[p-cnt])%mod;
}
cout<<ans;
}
E. Boring Segments 2100 线段树 2 pointers gq!
https://codeforces.com/contest/1555/problem/E
题解：对于有两个值需要考虑的时候，我们可以选择二分或双指针，我们可以枚举最小值x，试确定最小的可能最大值，定为f(x),显然f(x)是不减的。那么我们可以考虑双指针，我们把线段按照w从小到大排序，每次删去小于左指针的，然后不断增大右指针直到1-m每个区间都被覆盖。如何增删区间呢？我们可以使用线段树，节点i表示[i,i+1]上被区间经过了多少次，区间最小值>0时即满足题意，可logm维护，总复杂度nlogn+nlogm。
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+10;
struct node{
int l,r,w;
}t[N*4];
struct qwq{
int u,v,w;
}b[N];
bool cmp(qwq x,qwq y){
return x.w<y.w;
}
int lz[N*4],a[N];
void build(int p,int l,int r){
t[p].l=l,t[p].r=r;
if(t[p].l==t[p].r){
t[p].w=0;return;
}
int mid=(l+r)/2;
build(p*2,l,mid);
build(p*2+1,mid+1,r);
t[p].w=min(t[p*2].w,t[p*2+1].w);
}
void spread(int p){
if(lz[p]==1e18) return;
t[p*2].w+=lz[p];
t[p*2+1].w+=lz[p];
lz[p*2]+=lz[p];
lz[p*2+1]+=lz[p];
lz[p]=0;
}
void change(int p,int l,int r,int k){
if(l<=t[p].l&&t[p].r<=r){
t[p].w+=k;
lz[p]+=k;
return;
}
spread(p);
int mid=(t[p].l+t[p].r)/2;
if(l<=mid) change(2*p,l,r,k);
if(r>mid) change(2*p+1,l,r,k);
t[p].w=min(t[p*2].w,t[p*2+1].w);
}
int ask(int p,int l,int r){
if(t[p].l>=l&&t[p].r<=r){
return t[p].w;
}
spread(p);
int mid=(t[p].l+t[p].r)/2,res=1e18;
if(l<=mid) res=min(ask(p*2,l,r),res);
if(r>mid) res=min(ask(p*2+1,l,r),res);
return res;
}
signed main(){
int n,m;cin>>n>>m;
for(int i=1;i<=n;i++){
int l,r,w;cin>>l>>r>>w;
b[i]={l,r,w};
}
build(1,1,m-1);
sort(b+1,b+n+1,cmp);
int p=1,ans=1e18;
for(int i=1;i<=n;i++){
if(i!=1){
auto [u,v,w]=b[i-1];
change(1,u,v-1,-1);
}
while(p<=n){
if(ask(1,1,m-1)==0){
int x=b[p].u,y=b[p].v;
change(1,x,y-1,1);
p++;
}
else{
break;
}
}
if(ask(1,1,m-1)>0)
ans=min(ans,b[p-1].w-b[i].w);
}
cout<<ans;
}