UESTC数据结构专题训练 G,H,I,J

G,http://acm.uestc.edu.cn/#/problem/show/1598

题意：给你一个n个元素的序列，支持以下操作：单点修改，查询区间内连续的最大子段和。

解法：线段树每个结点维护四个域：maxv，maxl，maxr，sumv，其中sumv为该区间的和，maxv为该区间上的最大子段和，maxl为必须包含左端点的最大子段和，maxr为必须包含右端点的最大子段和。之后我们用lc和rc表示左子节点和右子节点。

修改时：
1、若 lc.maxr 和 rc.maxl 都为负，就从中取较大的为该节点的maxv（防止一个都不取），反之取二者中正的（都正就都取）。
2、将该节点的 maxv 用 lc 和 rc 的 maxv 更新。
3、该节点的 maxl 为 max { lc.maxl , lc.sumv + rc.maxl }。
4、该节点的 maxr 为 max { rc.maxr , rc.sumv + lc.maxr }。
5、该节点的 sumv 为 lc.sumv + rc.sumv 。

查询时：
按照修改的方式将询问区间覆盖的结点信息合并即可。


#include <bits/stdc++.h>
using namespace std;
const int maxn = 500010;
struct node{
    int l,r,lm,rm,mx,sum;
}tree[maxn<<2];
int n,m,a[maxn];
void pushup(int rt){
    tree[rt].sum=tree[rt<<1].sum+tree[rt<<1|1].sum;
    tree[rt].lm=max(tree[rt<<1].lm,tree[rt<<1].sum+tree[rt<<1|1].lm);
    tree[rt].rm=max(tree[rt<<1|1].rm,tree[rt<<1].rm+tree[rt<<1|1].sum);
    tree[rt].mx=max(max(tree[rt<<1].mx,tree[rt<<1|1].mx),tree[rt<<1].rm+tree[rt<<1|1].lm);
}
void build(int l, int r, int rt){
    tree[rt].l=l,tree[rt].r=r;
    if(l==r){
        tree[rt].sum=tree[rt].lm=tree[rt].rm=tree[rt].mx=a[l];
        return;
    }
    int mid=(l+r)/2;
    build(l,mid,rt<<1);
    build(mid+1,r,rt<<1|1);
    pushup(rt);
}
void update(int pos, int val, int rt){
    if(tree[rt].l==tree[rt].r){
        tree[rt].sum=tree[rt].lm=tree[rt].rm=tree[rt].mx=val;
        return;
    }
    int mid=(tree[rt].l+tree[rt].r)/2;
    if(pos<=mid) update(pos,val,rt<<1);
    else update(pos,val,rt<<1|1);
    pushup(rt);
}
node query(int L, int R, int rt){
    if(L<=tree[rt].l&&tree[rt].r<=R){
        return tree[rt];
    }
    int mid=(tree[rt].l+tree[rt].r)/2;
    if(R<=mid) return query(L,R,rt<<1);
    else if(L>mid) return query(L,R,rt<<1|1);
    else{
            node a,g,h;
            g=query(L,mid,rt<<1);
            h=query(mid+1,R,rt<<1|1);
            a.mx=max(max(g.mx,h.mx),g.rm+h.lm);
            a.rm=max(h.rm,g.rm+h.sum);
            a.lm=max(g.lm,g.sum+h.lm);
            return a;
    }
}
int main()
{
    int n, m;
    while(~scanf("%d%d",&n,&m)){
        for(int i=1; i<=n; i++) scanf("%d", &a[i]);
        build(1,n,1);
        while(m--){
            int op,l,r;
            scanf("%d %d %d", &op, &l, &r);
            if(op==1){
                printf("%d\n", query(l,r,1).mx);
            }
            else{
                update(l,r,1);
            }
        }
    }
    return 0;
}

H，http://acm.uestc.edu.cn/#/problem/show/1581

题意：给你一个n个元素的序列，支持以下操作：单点修改，查询某个下标是等差数列的子序列的最小值

解法：乱搞题。设置一个阈值K，

当公差>K的时候，可以暴力计算答案。我这里设成5就过了。
当公差小于K的时候，对每一个公差d，及其所有小于等于d的首项，建立一棵线段树。注意，公差确定时，每个首项对应的线段树是没有交集的。
共O(K2)棵线段树，总空间为O(K*n)。
询问时，找到它究竟在哪棵线段树。
修改时，在K棵线段树中进行修改。


#include <bits/stdc++.h>
using namespace std;
const int maxn=70010;
int n,m,a[maxn],pos1[6][maxn],pos2[6][maxn];
struct seg{
    int c, tree[maxn<<2];
    void pushup(int rt){
        tree[rt]=max(tree[rt<<1],tree[rt<<1|1]);
    }
    void build(int l, int r, int rt){
        if(l==r){
            tree[rt]=a[pos2[c][l]];
            return;
        }
        int mid=(l+r)/2;
        build(l,mid,rt*2);
        build(mid+1,r,rt*2+1);
        pushup(rt);
    }
    void update(int pos, int l, int r, int rt){
        if(l==r){
            tree[rt]=a[pos2[c][l]];
            return;
        }
        int mid=(l+r)>>1;
        if(pos<=mid) update(pos,l,mid,rt<<1);
        else update(pos,mid+1,r,rt<<1|1);
        pushup(rt);
    }
    int query(int L, int R, int l, int r, int rt){
        if(L<=l&&r<=R){
            return tree[rt];
        }
        int mid=(l+r)>>1;
        if(R<=mid) return query(L,R,l,mid,rt<<1);
        else if(L>mid) return query(L,R,mid+1,r,rt<<1|1);
        else{
            return max(query(L,mid,l,mid,rt<<1),query(mid+1,R,mid+1,r,rt<<1|1));
        }
    }
}T[6];

int main()
{
    while(~scanf("%d", &n)){
        for(int i=1; i<=n; i++) scanf("%d", &a[i]);
        for(int i=1; i<=5; i++){
            int now=1,tot=1;
            for(int j=1; j<=n; j++){
                pos1[i][now]=j;
                pos2[i][j]=now;
                now+=i;
                if(now>n) now=++tot;
            }
            T[i].c=i;
            T[i].build(1,n,1);
        }
        scanf("%d", &m);
        while(m--){
            int op,x,y;
            scanf("%d %d %d",&op,&x,&y);
            if(op==0){
                a[x]+=y;
                for(int i=1; i<=5; i++){
                    T[i].update(pos1[i][x],1,n,1);
                }
            }
            else{
                if(y<=5){
                    int r=pos1[y][x]+(n-x)/y;
                    printf("%d\n", T[y].query(pos1[y][x],r,1,n,1));
                }
                else{
                    int ans=a[x];
                    for(int i=x; i<=n; i+=y){
                        ans=max(ans,a[i]);
                    }
                    printf("%d\n",ans);
                }
            }
        }
    }
    return 0;
}

I,http://acm.uestc.edu.cn/#/problem/show/1603

题意：现在有一个序列

解法如下：

用set维护，set中存储的是个pair第一维权值，第二维是在原序列的下标。
贪心地从前往后扫，每到一个元素，就查找之前的元素中小于等于其的最大的元素//it=Set.lower_bound(pair<a[i],i>);it--;//，如果存在，就将它置为其父亲。如果一个结点已经是两个儿子的父亲了，就不能在set中存在了，就将他删除。如果然后将当前元素插入。
pair的比较函数是双关键字比较，先按第一关键字，如果相同，再按第二关键字。
如果不存在，就直接将当前元素插入。
证明是比较显然的，因为对于某个元素，前面各个堆中权值相同的结点都是等价的。
输出答案时用邻接表/*vector<int>G[N];*/把树存下来，跑个dfs，然后排个序输出就行。

复杂度:O(n*log(n)*log(n))


#include <bits/stdc++.h>
using namespace std;
const int maxn = 100010;
int n, cnt, a[maxn], son[maxn];
vector <int> G[maxn];
struct node{
    int first,second;
};
bool operator<(node x, node y){
    if(a[x.second]==a[y.second]) return x.second<y.second;
    return a[x.second]<a[y.second];
}
set<node>s;

int main()
{
    int T;
    scanf("%d",&T);
    while(T--){
        s.clear();
        cnt=0;
        scanf("%d", &n);
        memset(son,0,sizeof(son));
        //for(int i=0; i<maxn; i++) G[i].clear();
        for(int i=1; i<=n; i++){
            scanf("%d",&a[i]);
            node now;
            now.second=i;
            set<node>::iterator it=s.upper_bound(now);
            if(it==s.begin()){
                G[cnt].push_back(i);
                now.first=cnt,now.second=i;
                s.insert(now);
                cnt++;
            }
            else{
                it--;
                now=*it;
                son[now.second]++;
                if(son[now.second]==2) s.erase(it);
                now.second=i;
                s.insert(now);
                G[now.first].push_back(i);
            }
        }
        printf("%d\n", cnt);
        for(int i=0; i<cnt; i++){
            printf("%d",G[i].size());
            for(int j=0; j<G[i].size(); j++){
                printf(" %d", G[i][j]);
            }
            printf("\n");
            G[i].clear();
        }
    }
    return 0;
}

J，http://acm.uestc.edu.cn/#/problem/show/1599

题意：给你n个数，你每次可以合并两个数，合并所得的数是原来两个数之和，合并的代价也是原来两个数之和。n-1次合并后只剩一个数，问你该过程的最小代价。
解法：贪心用堆来维护，将所有元素放进堆。每次取出当前最小的两个元素，将其合并，统计答案，放回堆。重复n-1次。比较显然，先合并小的，再合并大的明显更优。


#include <bits/stdc++.h>
using namespace std;
priority_queue<int,vector<int>,greater<int> >q;
int n, x, ans;
int main()
{
    while(~scanf("%d", &n)){
        ans=0;
        while(!q.empty()) q.pop();
        for(int i=1; i<=n; i++){
            scanf("%d", &x);
            q.push(x);
        }
        while(q.size()>1){
            int cur = q.top(); q.pop();
            int cur1 = q.top(); q.pop();
            ans += cur+cur1;
            q.push(cur+cur1);
        }
        printf("%d\n", ans);
    }
    return 0;
}