跳转至

2020-08-02线段树

http://icpc.upc.edu.cn/problem.php?id=3756

题目描述

从前有一个贸易市场，在一位执政官到来之前都是非常繁荣的，自从他来了之后，发布了一系列奇怪的政令，导致贸易市场的衰落。 有n个商贩，从 0∼n−1编号，每个商贩的商品有一个价格 ai，有两种政令： 1.l,r,c，对于 i∈[l,r],ai←ai+c 2.l,r,d，对于 i∈[l,r],ai←⌊ai/d⌋,ai ←⌊ai/d⌋ 现在有一个外乡的旅客想要了解贸易市场的信息，有两种询问方式： 1.给定 l,r，求 mini∈[l,r]ai 2.给定 l,r，求 ∑i∈[l,r]ai

输入

第一行为两个空格隔开的整数 n,q分别表示商贩个数和政令 + 询问个数。 第二行包含n个由空格隔开的整数 a0∼an−1 接下来q行，每行表示一个操作，第一个数表示操作编号 1∼4接下来的输入和问题描述一致。

输出

对于每个 3、4 操作，输出询问答案。

样例输入
10 10
-5 -4 -3 -2 -1 0 1 2 3 4
1 0 4 1
1 5 9 1
2 0 9 3
3 0 9
4 0 9
3 0 1
4 2 3
3 4 5
4 6 7
3 8 9
样例输出

-2
-2
-2
-2
0
1
1
这道题目主要考查了线段树的标记和下放及将除法转为减法的思想，统计每一段的max和min，判断最大值和最小值经过除法以后所减掉的数字是否相同，如果相同，则这一段都可以减掉这个数字，下放标记即可。

#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3,"Ofast","inline")
#include<bits/stdc++.h>
#define inf 0x3f3f3f
using namespace std;
typedef long long ll;
ll num[400500]={0};
ll sum[400500]={0};
ll minn[400500]={0};
ll maxx[400500]={0};
ll lazy[400500]={0};
ll pushup(ll t)
{
    sum[t]=sum[2*t]+sum[2*t+1];
    maxx[t]=max(maxx[2*t],maxx[2*t+1]);
    minn[t]=min(minn[2*t],minn[2*t+1]);
}
ll pushlazy(ll t,ll lz,ll len)
{
    sum[t]+=lz*len;
    minn[t]+=lz;
    maxx[t]+=lz;
    lazy[t]+=lz;
}
ll pushdown(ll l,ll r,ll t)
{
    if(lazy[t]!=0)
    {
        ll mid=(l+r)/2;
        pushlazy(2*t,lazy[t],mid-l+1);
        pushlazy(2*t+1,lazy[t],r-mid);
        lazy[t]=0;
    }
}
ll build(ll l,ll r,ll t)
{
    lazy[t]=0;
    if(l==r)
    {
        sum[t]=minn[t]=maxx[t]=num[l];
        return 0;
    }
    ll mid=(l+r)/2;
    build(l,mid,t*2);
    build(mid+1,r,2*t+1);
    pushup(t);
}
ll add(ll x,ll l,ll r,ll L,ll R,ll t)
{
    if(l>=L&&r<=R)
    {
        lazy[t]+=x;
        sum[t]+=(r-l+1)*x;
        minn[t]+=x;
        maxx[t]+=x;
        return 0;
    }
    pushdown(l,r,t);
    ll mid=(l+r)/2;
    if(L<=mid)
        add(x,l,mid,L,R,2*t);
    if(R>mid)
        add(x,mid+1,r,L,R,2*t+1);
    pushup(t);
}
ll div(ll x,ll l,ll r,ll L,ll R,ll t)
{
    if(l>=L&&r<=R)
    {
        ll A,B;
        if(minn[t]<0)
            A=(minn[t]-x+1)/x;
        else
            A=minn[t]/x;
        if(maxx[t]<0)
            B=(maxx[t]-x+1)/x;
        else
            B=maxx[t]/x;
        if(A-minn[t]==B-maxx[t])
        {
            pushlazy(t,B-maxx[t],r-l+1);
            return 0;
        }
    }
    pushdown(l,r,t);
    ll mid=(l+r)/2;
    if(L<=mid)
        div(x,l,mid,L,R,2*t);
    if(R>mid)
        div(x,mid+1,r,L,R,2*t+1);
    pushup(t);
}
ll querysum(ll l,ll r,ll L,ll R,ll t)
{
    if(l>=L&&r<=R)
        return sum[t];
    pushdown(l,r,t);
    ll mid=(l+r)/2;
    ll ans=0;
    if(L<=mid)
        ans+=querysum(l,mid,L,R,2*t);
    if(R>mid)
        ans+=querysum(mid+1,r,L,R,2*t+1);
    return ans;
}
ll querymin(ll l,ll r,ll L,ll R,ll t)
{
    if(l>=L&&r<=R)
        return minn[t];
    pushdown(l,r,t);
    ll mid=(l+r)/2;
    ll ans=inf;
    if(L<=mid)
        ans=min(querymin(l,mid,L,R,2*t),ans);
    if(R>mid)
        ans=min(querymin(mid+1,r,L,R,2*t+1),ans);
    return ans;
}
int main()
{
    ll n,m,a,b,c,d;
    scanf("%lld%lld",&n,&m);
    for(ll i=1;i<=n;i++)
        scanf("%lld",&num[i]);
    build(1,n,1);
    for(ll i=1;i<=m;i++)
    {
        scanf("%lld",&a);
        if(a==1)
        {
            scanf("%lld%lld%lld",&b,&c,&d);
            add(d,1,n,b+1,c+1,1);
        }
        else if(a==2)
        {
            scanf("%lld%lld%lld",&b,&c,&d);
            div(d,1,n,b+1,c+1,1);
        }
        else if(a==3)
        {
            scanf("%lld%lld",&b,&c);
            printf("%lld\n",querymin(1,n,b+1,c+1,1));
        }
        else
        {
            scanf("%lld%lld",&b,&c);
            printf("%lld\n",querysum(1,n,b+1,c+1,1));
        }
    }
}
http://icpc.upc.edu.cn/problem.php?cid=2512&pid=4

题目描述

licunchun 在划水。

licunchun 最近迷上了一款打怪兽的游戏。

n个怪兽站成了一排，每个怪兽都有一个防御值ai。

licunchun 会按照一种奇怪的顺序打怪兽。

对于每一次打怪兽，licunchun 需要找到怪兽序列中出现次数大于等于2的防御最小值x，找到x的2个最小下标i,j，将第i个怪兽打死并从序列中除去，将第j个怪兽的防御值aj改为2x。

licunchun 想知道，在反复进行打怪兽后，怪兽序列的最终状态是怎样的。

输入

共2行。

第1行，输入正整数n，表示怪兽个数。

第1行，输入第i个怪兽的防御值ai。

输出

共2行。

第1行，输出剩余怪兽个数ans。

第2行，共ans数，按顺序输出仍然在怪兽序列中的怪兽的防御值ai。

样例输入
7
3 4 1 2 2 1 1
样例输出

4
3 8 2 1
提示 在这里插入图片描述 简单的模拟，priority_queue和pair结合起来使用 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll a[155000]={0};
typedef pair<ll,ll> node_pair;
priority_queue<node_pair,vector<node_pair>,greater<node_pair> > q;
int main()
{
    ll n;
    scanf("%lld",&n);
    for(ll i=1;i<=n;i++)
    {
        scanf("%lld",&a[i]);
        q.push(make_pair(a[i],i));
    }
    while(q.size()!=1)
    {
        node_pair b1=q.top();
        q.pop();
        node_pair b2=q.top();
        if(b1.first==b2.first)
        {
            a[b2.second]*=2;
            a[b1.second]=-1;
            q.pop();
            q.push(make_pair(a[b2.second],b2.second));
        }
    }
    queue<ll>w;
    for(ll i=1;i<=n;i++)
    {
        if(a[i]!=-1)
            w.push(a[i]);
    }
    printf("%d\n",w.size());
    while(!w.empty())
    {
        printf("%lld ",w.front());
        w.pop();
    }
    return 0;
}
http://icpc.upc.edu.cn/problem.php?cid=2512&pid=6

题目描述

licunchun 找到了一张画。

licunchun 学习了膜法，想要一块一块地，让里面的颜色消失。

照片的颜色只有一行。licunchun 每次可以选择中间一段相同颜色的一段直接让它消失。

licunchun 想知道所需要的最少次数。

licunchun 冥思苦想了1145141919810都没有想出来，于是把问题交给了你。

输入

第一行输入T，表示数据组数

对于每组数据：

第一行给定一个n，表示照片的长度。

第二行，给定一串s，用来描述这个照片的颜色。为了方便，颜色的描述统一用小写字母，一种字母表示一种颜色。

输出

对于每组数据T，一行输出一个数字，表示所需要的最少次数。

样例输入
3
5
abaca
8
abcddcba
7
lggmmro
样例输出
3
4
5
提示

在这里插入图片描述 动态规划，dp[i][j]代表以i为开头长度为j的最少操作次数，最后dp[1][n]即为答案。

#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3,"Ofast","inline")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int dp[600][600]= {0};
char a[600]="";
const int inf=0x3f3f3f;
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        memset(dp,inf,sizeof(dp));
        int n;
        scanf("%d",&n);
        scanf("%s",a+1);
        for(int i=1; i<=n; i++)
            dp[i][1]=1;
        for(int i=2; i<=n; i++)
        {
            for(int j=1; j<=n-i+1; j++)
            {
                if(a[j]==a[i+j-1])
                {
                    dp[j][i]=min(dp[j][i-1],dp[j+1][i-1]);
                }
                else
                {
                    dp[j][i]=min(dp[j][i-1],dp[j+1][i-1])+1;
                }
                for(int k=1;k<=i;k++)
                {
                    dp[j][i]=min(dp[j][i],dp[j][k]+dp[j+k][i-k]);
                }
            }
        }
        cout<<dp[1][n]<<endl;
    }
    return 0;
}
http://icpc.upc.edu.cn/problem.php?cid=2512&pid=2

题目描述

神仙姐姐遇到一个难题： 有宝藏出现在姐姐面前后，又出现一行字说“这里的各种类型的宝物是放在长方形的石桌上，你只能一次性拿走同一种类型的宝物，并且要求你拿走的宝物必须为某个正方形子矩阵中某条对角线，而且此时，你所选择的这个正方形子矩阵中，除了对角线位置，其它位置不能出现你所需要的宝物类型（因为这样会分心）！你可以把石桌视为01矩阵（0表示对应位置不是你所要的类型，1表示对应位置有你所要的类型，这样有助于你多拿些宝物）”。 当然爱美的姐姐选择的是可以美容养颜类型的，所以她把所想要的宝物(即美容水)用１表示，不想要的就用0表示。同时姐姐是个很贪婪(贪美)的神仙，所以她想一下拿走尽量多的她所要的美容品。请你帮神仙姐姐算一下，她一下最多可以拿多少个？

输入

第一行有两个整数n和m（n，m≥1），描述石桌的规模。接下来的n行，每行有m个数字（非“0”即“1”）。每两个数字之间用空格隔开。

输出

只有一个整数——神仙一下最多可以拿到多少个宝物，占一行，行末有回车。

样例输入
4 6
0 1 0 1 0 0
0 0 1 0 1 0
1 1 0 0 0 1
0 1 1 0 1 0
样例输出
3
提示

对于100%的数据，有n，m≤2500 二维前缀和

#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3,"Ofast","inline")
#include <bits/stdc++.h>
using namespace std;

int a[2550][2550]={0};
int d[2550][2550]={0};
int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1; i<=n; i++)
    {
        for(int j=1; j<=m; j++)
        {
            scanf("%d",&a[i][j]);
            d[i][j]=d[i-1][j]+d[i][j-1]-d[i-1][j-1]+a[i][j];
        }
    }
    int max1=0;
    for(int i=1; i<=n; i++)
    {
        for(int j=1; j<=m; j++)
        {
            int cnt=0;
            while(i+cnt<=n&&j+cnt<=m&&a[i][j]&&a[i+cnt][j+cnt])
            {
                int k1=d[i+cnt][j+cnt]-d[i-1][j+cnt]-d[i+cnt][j-1]+d[i-1][j-1];
                int k2=d[i+cnt-1][j+cnt-1]-d[i-1][j+cnt-1]-d[i+cnt-1][j-1]+d[i-1][j-1];
                if(k1==cnt+1&&k1-k2==1)
                {
                    max1=max(max1,cnt+1);
                    cnt++;
                }
                else
                    break;
            }
            cnt=0;
            while(i+cnt<=n&&j-cnt>=1&&a[i][j]&&a[i+cnt][j-cnt])
            {
                int k1=d[i+cnt][j]-d[i-1][j]-d[i+cnt][j-cnt-1]+d[i-1][j-1-cnt];
                int k2=d[i+cnt-1][j]-d[i-1][j]-d[i+cnt-1][j-cnt]+d[i-1][j-cnt];
                if(k1==cnt+1&&k1-k2==1)
                {
                    max1=max(max1,cnt+1);
                    cnt++;
                }
                else
                    break;
            }
        }
    }
    cout<<max1<<endl;
    return 0;
}