C：直接单独算每个位置的贡献，如果当前位置和前面位置重复了，那么前面就没选的位置了
修改的时候只要重新算i和i+1位置即可
#include<bits/stdc++.h>
using namespace std;
const int N=3e5+10,M=2*N,mod=1e9+7;
#define int long long
#define uLL unsigned long long
const long long inf=1e18;
typedef pair<int,int> PII;
typedef long long LL;
using node=tuple<int,int,int>;
int n,m,k;
int a[N];
int calc(int i){
int res=0;
int k=n-i+1;
if(a[i]==a[i-1]) return k;
return (n-i+1)*(i);
}
void solve()
{
cin>>n>>m;
int s=0;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1;i<=n;i++){
s+=calc(i);
}
a[n+1]=0;
while(m--){
int x,y;cin>>x>>y;
s-=calc(x);
s-=calc(x+1);
a[x]=y;
s+=calc(x);
s+=calc(x+1);
cout<<s<<"\n";
//cout<<calc((int)(st.size()))<<"\n";
}
}
signed main(){
cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
int t=1;
// cin>>t;
while(t--) solve();
return 0;
}D：
拆位，考虑字典序最小，让开头的数能等于0就等于0
要先把一定是0的数和u==v这种确定的数先填了，后面根据字典序填即可
#include<bits/stdc++.h>
using namespace std;
const int N=3e5+10,M=2*N,mod=1e9+7;
#define int long long
#define uLL unsigned long long
const long long inf=1e18;
typedef pair<int,int> PII;
typedef long long LL;
using node=tuple<int,int,int>;
int n,m,k;
int a[N];
vector<PII> g[N];
int now[N];
void solve()
{
cin>>n>>m;
vector<array<int,3>> a(m);
for(auto&i:a){
cin>>i[0]>>i[1]>>i[2];
g[i[0]].emplace_back(i[1],i[2]);
g[i[1]].emplace_back(i[0],i[2]);
}
vector<int> res(n+10);
for(int i=30;i>=0;i--)
{
memset(now,-1,sizeof(now));
for(int j=1;j<=n;j++){
for(auto [v,z]:g[j]){
if(v==j){
now[j]=(z>>i&1);continue;
}
if(z>>i&1) continue;
now[j]=now[v]=0;
}
}
for(int j=1;j<=n;j++)
{
if(g[j].size()==0)
{
now[j]=0;
}
if(now[j]!=-1) continue;
for(auto [v,z]:g[j])
{
if(now[v]==0)//另一个固定了，j只能是1
{
now[j]=1;
break;
}
}
if(now[j]==-1)
{
for(auto [v,z]:g[j])
{
now[v]=1;
}
now[j]=0;
}
}
for(int j=1;j<=n;j++)
res[j]+=(now[j])*(1<<i);
}
for(int i=1;i<=n;i++) cout<<res[i]<<" ";
}
signed main(){
cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
int t=1;
//cin>>t;
while(t--) solve();
return 0;
}E：
直接斜率优化
考虑每层k进行斜率优化，毕竟转移只会从i-1转移到i层
f[i]=min(f[j]+(i-j)^2)
根据斜率优化式子
f[i]=f[j]+i*i-2*i*j+j*j
f[j]+j*j=2*i*j+f[i]-i*i
y=f[j]+j*j
k=2*i
b=f[i]-i*i
y=kx-b
当i确定的时候让b最小，f[i]一定最小
直接维护凸包即可
#include<bits/stdc++.h>
using namespace std;
const int N=3e5+10,M=2*N,mod=1e9+7;
#define int long long
#define uLL unsigned long long
const long long inf=1e18;
typedef pair<int,int> PII;
typedef long long LL;
using node=tuple<int,int,int>;
int n,m,k;
int a[N];
vector<PII> g[N];
int now[N];
void solve()
{
cin>>n>>m;
vector<array<int,3>> a(m);
for(auto&i:a){
cin>>i[0]>>i[1]>>i[2];
g[i[0]].emplace_back(i[1],i[2]);
g[i[1]].emplace_back(i[0],i[2]);
}
vector<int> res(n+10);
for(int i=30;i>=0;i--)
{
memset(now,-1,sizeof(now));
for(int j=1;j<=n;j++){
for(auto [v,z]:g[j]){
if(v==j){
now[j]=(z>>i&1);continue;
}
if(z>>i&1) continue;
now[j]=now[v]=0;
}
}
for(int j=1;j<=n;j++)
{
if(g[j].size()==0)
{
now[j]=0;
}
if(now[j]!=-1) continue;
for(auto [v,z]:g[j])
{
if(now[v]==0)//另一个固定了，j只能是1
{
now[j]=1;
break;
}
}
if(now[j]==-1)
{
for(auto [v,z]:g[j])
{
now[v]=1;
}
now[j]=0;
}
}
for(int j=1;j<=n;j++)
res[j]+=(now[j])*(1<<i);
}
for(int i=1;i<=n;i++) cout<<res[i]<<" ";
}
signed main(){
cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
int t=1;
//cin>>t;
while(t--) solve();
return 0;
}
