Lvat_s Blog

很多人都是使用大型数据结构写的。

我是整体二分+树状数组维护，思路是Zig_Zag大神博客上的。

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<set>
#include<algorithm>
using namespace std;
 
const int N=30005,M=1000005;
 
int n,m,col[N],cnt,num,BIT[N],ans[N],tmp[N];
set<int> Color[M];
 
struct Ask{
int l,r,opt,cur,id;
}ask[N],Q1[N],Q2[N];
 
int lowbit(int x){return x&(-x);}
void Add(int pos,int val){while(pos<=n){BIT[pos]+=val;pos+=lowbit(pos);}}
int Sum(int pos){int ans=0;while(pos){ans+=BIT[pos];pos-=lowbit(pos);}return ans;}
int Pre(int x,int c){set<int>::iterator I=Color[c].lower_bound(x);if(I!=Color[c].begin())return *(--I);return 0;}
int Nxt(int x,int c){set<int>::iterator I=Color[c].upper_bound(x);if(I!=Color[c].end())return *I;return 0;}
 
void Div2x(int l,int r,int nl,int nr){
if(nl>nr)return;
int mid=l+r>>1,M1=0,M2=0;
if(l==r){for(int i=nl;i<=nr;i++)if(ask[i].opt==3)ans[ask[i].id]=ask[i].cur;return;}
for(int i=nl;i<=nr;i++){
    if(ask[i].opt==1 && ask[i].r<=mid)Add(ask[i].l,1);
    if(ask[i].opt==2 && ask[i].r<=mid)Add(ask[i].l,-1);
    if(ask[i].opt==3)tmp[i]=Sum(ask[i].r)-Sum(ask[i].l-1);
}
for(int i=nl;i<=nr;i++){
    if(ask[i].opt==1 && ask[i].r<=mid)Add(ask[i].l,-1);
    if(ask[i].opt==2 && ask[i].r<=mid)Add(ask[i].l,1);
}
for(int i=nl;i<=nr;i++){
    if(ask[i].opt==3){
        if(ask[i].l<=mid)Q1[++M1]=ask[i];
        else {ask[i].cur+=tmp[i];Q2[++M2]=ask[i];}
    }
    else {
        if(ask[i].r<=mid)Q1[++M1]=ask[i];
        else Q2[++M2]=ask[i];
    }
}
for(int i=1;i<=M1;i++)ask[nl+i-1]=Q1[i];
for(int i=1;i<=M2;i++)ask[nr-M2+i]=Q2[i];
Div2x(l,mid,nl,nl+M1-1);
Div2x(mid+1,r,nl+M1,nr);
}
 
int main(){
freopen("2120.in","r",stdin);
freopen("2120.out","w",stdout);
scanf("%d %d",&n,&m);
for(int i=1;i<=n;i++){
    scanf("%d",&col[i]);
    Color[col[i]].insert(i);
    ask[++num].opt=1;
    int p=Pre(i,col[i]);
    ask[num].l=i;
    ask[num].r=p;
}
for(int i=1;i<=m;i++){
    char s[5];
    int l,r;
    scanf("%s %d %d",s,&l,&r);
    if(s[0]=='Q'){
        ask[++num].opt=3;
        ask[num].id=++cnt;
        ask[num].l=l;
        ask[num].r=r;
    }
    else {
        int Ll=Pre(l,col[l]),Lr=Pre(l,r),Rl=Nxt(l,col[l]),Rr=Nxt(l,r);
        if(Rl){
            ask[++num].opt=2;ask[num].l=Rl;ask[num].r=l;
            ask[++num].opt=1;ask[num].l=Rl;ask[num].r=Ll;
        }
        ask[++num].opt=2;ask[num].l=l;ask[num].r=Ll;
        ask[++num].opt=1;ask[num].l=l;ask[num].r=Lr;
        if(Rr){
            ask[++num].opt=2;ask[num].l=Rr;ask[num].r=Lr;
            ask[++num].opt=1;ask[num].l=Rr;ask[num].r=l;
        }
        Color[col[l]].erase(l);
        Color[r].insert(l);
        col[l]=r;
    }
}
Div2x(0,M,1,num);
for(int i=1;i<=cnt;i++)printf("%d\n",ans[i]);
return 0;
}

树链剖分入门题

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
using namespace std;
 
const int N=100005;
 
int n,m,dep[N],fa[N],son[N],siz[N],en,h[N],pre[N],segn,id[N],top[N];
long long a[N];
 
struct Edge{
int b,next;
}e[N<<1];
 
void AddEdge(int sa,int sb){
e[++en].b=sb;
e[en].next=h[sa];
h[sa]=en;
}
 
struct SegTree{
int l,r;
long long sum,tag;
}tree[N<<2];
 
void Pushdown(int rt){
if(tree[rt].tag){
    tree[rt<<1].tag+=tree[rt].tag;
    tree[rt<<1|1].tag+=tree[rt].tag;
    tree[rt<<1].sum+=tree[rt].tag*(tree[rt<<1].r-tree[rt<<1].l+1ll);
    tree[rt<<1|1].sum+=tree[rt].tag*(tree[rt<<1|1].r-tree[rt<<1|1].l+1ll);
    tree[rt].tag=0;
}
}
 
void Pushup(int rt){
tree[rt].sum=tree[rt<<1].sum+tree[rt<<1|1].sum;
}
 
void Build(int rt,int l,int r){
tree[rt].l=l;tree[rt].r=r;
if(l==r){tree[rt].sum=a[pre[l]];return;}
int mid=l+r>>1;
Build(rt<<1,l,mid);Build(rt<<1|1,mid+1,r);
Pushup(rt);
}
 
void Add(int rt,int l,int r,long long val){
if(l<=tree[rt].l && tree[rt].r<=r){tree[rt].sum+=val*(tree[rt].r-tree[rt].l+1);tree[rt].tag+=val;return;}
int mid=tree[rt].l+tree[rt].r>>1;
Pushdown(rt);
if(l<=mid)Add(rt<<1,l,r,val);
if(r>mid)Add(rt<<1|1,l,r,val);
Pushup(rt);
}
 
long long Sum(int rt,int l,int r){
if(l<=tree[rt].l && tree[rt].r<=r)return tree[rt].sum;
int mid=tree[rt].l+tree[rt].r>>1;
long long ans=0;
Pushdown(rt);
if(l<=mid)ans+=Sum(rt<<1,l,r);
if(r>mid)ans+=Sum(rt<<1|1,l,r);
return ans;
}
 
void dfs1(int u,int Fa){
dep[u]=dep[Fa]+1;
fa[u]=Fa;
siz[u]=1;
son[u]=0;
for(int i=h[u];i;i=e[i].next){
    int v=e[i].b;
    if(v==Fa)continue;
    dfs1(v,u);
    siz[u]+=siz[v];
    if(siz[son[u]]<siz[v])son[u]=v;
}
}
 
void dfs2(int u,int ux){
top[u]=ux;
id[u]=++segn;
pre[segn]=u;
if(!son[u])return;
dfs2(son[u],ux);
for(int i=h[u];i;i=e[i].next){
    int v=e[i].b;
    if(v!=fa[u] && v!=son[u])dfs2(v,v);
}
}
 
long long Ask(int u){
int Tp=top[u];
long long ans=0;
while(Tp!=top[1]){
    ans+=Sum(1,id[Tp],id[u]);
    u=fa[Tp];
    Tp=top[u];
}
return ans+Sum(1,id[Tp],id[u]);
}
 
int main(){
freopen("4034.in","r",stdin);
freopen("4034.out","w",stdout);
scanf("%d %d",&n,&m);
for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
for(int i=1;i<n;i++){
    int u,v;
    scanf("%d %d",&u,&v);
    AddEdge(u,v);AddEdge(v,u);
}
dfs1(1,1);
dfs2(1,1);
Build(1,1,n);
while(m--){
    int opt,u;
    long long val;
    scanf("%d %d",&opt,&u);
    if(opt==1){scanf("%lld",&val);Add(1,id[u],id[u],val);}
    if(opt==2){scanf("%lld",&val);Add(1,id[u],id[u]+siz[u]-1,val);}
    if(opt==3)printf("%lld\n",Ask(u));
}
return 0;
}

这题是一个DP

每次考虑两棵子树的贡献，然后把两棵子树合并起来，中间的转移类似树上背包

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
 
const int N=2005;
 
int n,K,en,h[N],siz[N],vis[N];
long long dp[N][N],tp[N];
 
struct Edge{
int b,next;
long long v;
}e[N<<1];
 
void AddEdge(int sa,int sb,long long sc){
e[++en].b=sb;
e[en].v=sc;
e[en].next=h[sa];
h[sa]=en;
}
 
void DP(int u){
siz[u]=vis[u]=1;
for(int i=h[u];i;i=e[i].next){
    int v=e[i].b;
    if(vis[v])continue;
    DP(v);
    for(int j=0;j<=K;j++)tp[j]=dp[u][j];
    for(int j=0;j<=min(siz[u],K);j++){
        for(int k=0;k<=min(siz[v],K);k++){
            tp[j+k]=max(tp[j+k],dp[v][k]+dp[u][j]+e[i].v*(k*(K-k)+(siz[v]-k)*(n-K-(siz[v]-k))));
        }
    }
    siz[u]+=siz[v];
    for(int j=0;j<=siz[u];j++)dp[u][j]=max(dp[u][j],tp[j]);
}
}
 
int main(){
freopen("4033.in","r",stdin);
freopen("4033.out","w",stdout);
scanf("%d %d",&n,&K);
for(int i=1;i<n;i++){
    int u,v,w;
    scanf("%d %d %d",&u,&v,&w);
    AddEdge(u,v,w);AddEdge(v,u,w);
}
DP(1);
printf("%lld\n",dp[1][K]);
return 0;
}

直接数位DP不解释

好吧……记录一下相邻的差，然后搞一搞

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
using namespace std;
 
const long long N=15;
 
long long A,B,dp[N][10],a[N];
 
long long Abs(long long x){return x>0?x:-x;}
 
void Pre(){
memset(dp,0,sizeof(dp));
for(long long i=0;i<=9;i++)dp[1][i]=1;
for(long long i=2;i<=10;i++){
    for(long long j=0;j<=9;j++){
        for(long long k=0;k<=9;k++)if(Abs(j-k)>=2)dp[i][j]+=dp[i-1][k];
    }
}
}
 
long long DP(long long x){
if(x==0)return 0;
long long cnt=0,ans=0;
while(x){a[++cnt]=x%10;x/=10;}
for(long long i=1;i<=cnt/2;i++)swap(a[i],a[cnt-i+1]);
for(long long i=1;i<a[1];i++)ans+=dp[cnt][i];
for(long long i=1;i<cnt;i++){
    for(long long j=1;j<=9;j++)ans+=dp[i][j];
}
for(long long i=2;i<=cnt;i++){
    for(long long j=0;j<a[i];j++)if(Abs(j-a[i-1])>=2)ans+=dp[cnt-i+1][j];
    if(Abs(a[i]-a[i-1])<2)break;
}
return ans;
}
 
int main(){
freopen("1026.in","r",stdin);
freopen("1026.out","w",stdout);
scanf("%lld %lld",&A,&B);
Pre();
printf("%lld\n",DP(B+1)-DP(A));
return 0;
}

从我更新了那篇AFO博文后，有一段时间没上博客了

今天上了下发现还是有人来看的……

我才高一，哪能轻易AFO!

对了，THUSC滚大粗了，rky一百七十多分被卡协议了

结果是THUSC PKUSC我校全军覆没，无一人签协议(已经有的不算)

嗯……最近做题量也减少了

不能颓废了。虽然去不了NOI，但是明年应该没问题(Flag)

好好努力吧。