2018-07-08

早上继续NewTrain

NewTrain7 bzoj 3155 Preprefix sum

题解:
这题比较简单
首先发现我们要算的实质上是a_l*(r-l+1)+a_{l+1}*(r-l)+…+a_r*1
这个东西还是很好维护的
一种简单的方法是:
a_l*(r-l+1)+a_{l+1}*(r-l)+…+a_r*1 =a_l*(n-l+1)+a_{l+1}*(n-l)+...+a_r*(n-r+1)-\sum_{i=l}^r {a_i}*(n-r)
那么我们维护两个树状数组 第一个存储区间和 第二个存储带权区间和 也就是\sum_{i=1}^k{a_i*(n-i+1)} 询问的时候相减即可
Code:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define lowbit(x) (x&(-x))
struct BIT{
    ll a[200100];
 
    void init(){memset(a,0,sizeof(a));}
     
    ll ask(int pos){
        ll ret=0;
        while(pos){
            ret+=a[pos];
            pos-=lowbit(pos);
        }
        return ret;
    }
 
    void add(int pos,ll nw){
        while(pos<200000){
            a[pos]+=nw;
            pos+=lowbit(pos);
        }
    }
} b1,b2;
 
int n,m;
int a[100100];
 
int main(){
    scanf("%d%d",&n,&m);
    for(register int i=1;i<=n;i++){
        scanf("%d",a+i);
        b1.add(i,a[i]);
        b2.add(i,a[i]*1ll*(n-i+1));
    }
     
    while(m--){
        char c[11];
        scanf("%s",&c);
        if(c[0]=='Q'){
            int pos;
            scanf("%d",&pos);
            printf("%lld\n",b2.ask(pos)-b1.ask(pos)*(n-pos));
        }
        else{
            int pos,x;
            scanf("%d%d",&pos,&x);
            b1.add(pos,x-a[pos]);
            b2.add(pos,(x-a[pos])*1ll*(n-pos+1));
            a[pos]=x;
        }
    }
    return 0;
}

NewTrain7 bzoj2429 聪明的猴子

题解:
水题
求一个最小生成树 找到其中的最大的边 然后计算有多少个猴子的能力值大于等于这条边的长度
Code:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll read(){
    ll x=0,f=1;char c=getchar();
    while(c<'0' || c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0' && c<='9'){x=x*10+c-'0';c=getchar();}
    return x*f;
}

int n,m;
int a[555];
pair<int,int> pos[1010];
struct Edge{
    int fr,to;
    double len;
    bool operator <(Edge ano) const{
        return len<ano.len;
    }
} ed[1000100];
int cnt;
int fa[1010];

double calc(pair<int,int> a,pair<int,int> b){
    return sqrt((a.first-b.first)*(a.first-b.first)+(a.second-b.second)*(a.second-b.second));
}
int fp(int x){
    if(fa[x]==x) return x;
    return fa[x]=fp(fa[x]);
}

int main(){
    #ifdef LZT
    freopen("in","r",stdin);
    #endif
    m=read();
    for(int i=1;i<=m;i++) a[i]=read();
    n=read();
    for(int i=1;i<=n;i++)
        pos[i].first=read(),pos[i].second=read();
    for(int i=1;i<=n;i++)
        for(int j=i+1;j<=n;j++)
            ed[++cnt]=(Edge){i,j,calc(pos[i],pos[j])};
    for(int i=1;i<=n;i++)
        fa[i]=i;
    sort(ed+1,ed+cnt+1);
    double ans=0;
    for(int i=1;i<=cnt;i++){
        int x=fp(ed[i].fr),y=fp(ed[i].to);
        if(x==y) continue;
        ans=max(ans,ed[i].len);
        fa[x]=y;
    }
    int ret=0;
    for(int i=1;i<=m;i++)
        if(a[i]>=ans) ret++;
    cout<<ret<<endl;
    return 0;
}

NewTrain7 bzoj 2441 小W的问题