Three Sequences 2200
https://www.luogu.com.cn/problem/CF1406D
题解:贪心地想，令x为答案，则x应该为b的末项和c的首项，而每一步a(i)->a(i+1)若上升则b上升，若下降则c下降。故2x-a1>=up,2x-an>=down,解方程组可得到x值。
对于每步操作，它会使得l-1->l和r->r+1的上升/下降值发生变化，我们可以用差分数列+树状数组维护这种变化，复杂度为O(qlogn)。
代码：
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+10;
int a[N],c[N];
int ask(int x){
int ans=0;
for(;x;x-=x&-x) ans+=c[x];
return ans;
}
void ad(int x,int w){
for(;x<=1e5;x+=x&-x) c[x]+=w;
}
void add(int l,int r,int w){
ad(l,w);ad(r+1,-w);
}
int suan(int x){
if(x>=0) return (x+1)/2;
else{
return -((-x)/2);
}
}
signed main(){
int n;cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
int up=0,down=0;
ad(1,a[1]);
for(int i=2;i<=n;i++){
int d=a[i]-a[i-1];
ad(i,d);
if(d>=0) up+=d;
else down-=d;
}
up+=a[1],down+=a[n];
int ans=max(suan(up),suan(down));
cout<<ans<<endl;
int q;cin>>q;
for(int i=1;i<=q;i++){
int l,r,w;cin>>l>>r>>w;
if(l==1) up+=w;
if(r==n) down+=w;
if(w>=0){
if(l!=1){
int e=ask(l)-ask(l-1);
if(e<0&&e+w>=0)
down+=e,up+=e+w;
else if(e<0&&e+w<0)
down+=e,down-=e+w;
else if(e>=0)
up+=w;
}
if(r!=n){
int e=ask(r+1)-ask(r);
if(e>=0&&e-w<0){
up-=e;down-=e-w;
}
else if(e>=0&&e-w>=0) up-=e,up+=e-w;
else if(e<0) down-=-(e),down+=-(e-w);
}
}
else{
if(l!=1){
int e=ask(l)-ask(l-1);
if(e>=0&&e+w<0)
up-=e,down+=-(e+w);
else if(e>=0&&e+w>=0)
up-=e,up+=(e+w);
else if(e<0)
down+=-w;
}
if(r!=n){
int e=ask(r+1)-ask(r);
if(e<0&&e-w>=0){
down-=-e,up+=e-w;
}
else if(e<0&&e-w<0) down-=-e,down+=-(e-w);
else if(e>=0) up-=e,up+=e-w;
}
}
ans=max(suan(up),suan(down));
cout<<ans<<endl;
add(l,r,w);
}
}
Searchlights 2000
https://www.luogu.com.cn/problem/CF1408D
题解：我们可以维护上升x步后所需右移的最大步数f(x),易知图像必为阶梯状（若一灯处于另一灯的照明区域内则可去除），故下面的点需要右移的距离一定>=上面的点。我们首先可以确定两种解决方案，即一直向上或一直向前，若二者并非最优解，则一定是先走上再走右，而最优情况下一定有点上升到了与灯塔等高位置（因为需要其向右运动带出所有在其下面的点即所有未出去的点在此时有同样的右边界，而然高度越大显然可以使得目标更接近，其中一点到达灯塔高度即为某一右移长度下的临界条件，否则是答案一二之一）。那么我们可以枚举上升至各个灯塔高度时的最小右移距离，ans=max(fi)+x(i>=x).
代码：
#include<bits/stdc++.h>
using namespace std;
const int N=2e3+100;
const int M=1e6+100;
int ans,n,m,f[M],limit;
int a[N],b[N],c[N],d[N];
inline void ckmax(int &a,int b){
a=a<b?b:a;//让 a 取到 a,b 间较大值
}
inline void ckmin(int &a,int b){
a=a>b?b:a;//让 a 取到 a,b 间较小值
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
scanf("%d%d",&a[i],&b[i]);
for(int i=1;i<=m;i++)
scanf("%d%d",&c[i],&d[i]);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++){
if (d[j]<b[i]) continue;
ckmax(limit,d[j]-b[i]);
ckmax(f[d[j]-b[i]],c[j]-a[i]+1);
}
ans=limit+1;//只向右边走,走出边界
for(int i=limit,maxn=0;i>=0;i--){
ckmax(maxn,f[i]);ckmin(ans,i+maxn);
}
printf("%d",ans);
return 0;
}
Euclid's nightmare 2100
https://www.luogu.com.cn/problem/CF1466F
题解：由于1的个数只有1和2，对于2，容易想到是将i与j连边，使得任意联通块只有x-1条边，x个点（每个边代表一个向量，而若有多余边可以用其他边即环上另一条路径代替），对于只有1个1的点1，我们认为是将i与n+1相连，如此我们便可以得到A的大小与A中的元素，对于T我们容易用A推出：A中选择不同的边所形成的串一定不同，故T=ΣC(A,i)=2^(A).
代码：
#include<cmath>
#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>
#include<vector>
#include<map>
#define int long long
#define reg register
using namespace std;
const int maxn=5e5+5;
const int mod=1e9+7;
inline int read()
{
int x=0,f=1;
char ch=getchar();
while(ch<'0' || ch>'9')
{
if(ch=='-')
f=-1;
ch=getchar();
}
while(ch>='0' && ch<='9')
{
x=x*10+ch-'0';
ch=getchar();
}
return x*f;
}
int father[maxn];
int Find(int x)
{
if(father[x]!=x)
father[x]=Find(father[x]);
return father[x];
}
int n,m;
int s[maxn];
int tot=0;
int siz[maxn];
int v[maxn];
signed main()
{
v[0]=1;
n=read(),m=read();
for(int i=1;i<=max(n,m)+5;i++)
v[i]=v[i-1]*2%mod;
for(reg int i=1;i<=m+1;i++)
father[i]=i;
int cnt=0;
for(reg int i=1;i<=n;i++)
{
int k=read(),x,y;
if(k==1)
x=read(),y=m+1;
else
x=read(),y=read();
int nowx=Find(x),nowy=Find(y);
if(nowx==nowy)
continue;
father[nowx]=nowy;
s[++tot]=i;
}
int ans=v[tot]%mod;
printf("%lld %lld\n",ans,tot);
for(reg int i=1;i<=tot;i++)
printf("%lld ",s[i]);
printf("\n");
return 0;
}
D. Weight the Tree 2000
https://codeforces.com/problemset/problem/1646/D
题解：显然对于任意两个连接的点不能同时为好点（n=2特判），对于坏点显然取1最优，为了最小化sum我们可以考虑树形dp，dp方程f[u][0]=∑min(f[v][0],f[v][1]),f[u][1]=∑f[v][0]+d[u].再根据结果重新遍历一遍树选择最优的染色即可。