CF 419 div2

题解

B. Karen and Coffee
题意：
给出n个区间，对区间内的每一个数更新1次，给出一个整数k，然后给出q个区间，查询在每个区间内，有多少个数的更新次数是大于k的。
思路：
乍一看，以为是线段树模板，但是，不是这样的，但是这题是自己思考并且码出来了Orz。
首先，我们先写一个模板线段树，这样就可以查询到每个数被更新的次数，复杂度为nlgn，这个只用执行一次，然后再建立另外一颗线段树，用于查询大于等于k的个数就可以了，358ms，还是比较快的。
代码：

#include <string.h>
#include <stdio.h>
int a[200005];
int add[200005 << 2];
int sum[200005 << 2];
int num[200005 << 2];
const int u = 200000;
int n,k,q;
int ans = 0;
void pushup2(int rt)
{
    num[rt] = num[rt << 1] + num[rt << 1|1];
}
void build2(int l,int r,int rt)
{
    if (l == r)
    {
        if (a[l] >= k) num[rt] = 1;
        else num[rt] = 0;
        return;
    }
    int mid = (l + r) >> 1;
    build2(l,mid,rt << 1);
    build2(mid+1,r,rt << 1|1);
    pushup2(rt);
}
void query2(int ll,int rr,int l,int r,int rt)
{
    if (ll <= l && r <= rr)
    {
        ans += num[rt];
        return;
    }
    int mid = (l + r) >> 1;
    if (ll <= mid) query2(ll,rr,l,mid,rt << 1);
    if (rr > mid) query2(ll,rr,mid+1,r,rt << 1|1);
}
void pushup(int rt)
{
    sum[rt] = sum[rt << 1] + sum[rt << 1|1];
}
void build(int l,int r,int rt)
{
    if (l == r)
    {
        sum[rt] = 0;
        return;
    }
    int m = (l+r) >> 1;
    build(l,m,rt << 1);
    build(m+1,r,rt << 1|1);
    pushup(rt);
}
void pushdown(int rt,int ln,int rn)
{
    if (add[rt])
    {
        add[rt << 1] += add[rt];
        add[rt << 1|1] += add[rt];
        sum[rt << 1] += ln * add[rt];
        sum[rt << 1|1] += rn *add[rt];
        add[rt] = 0;
    }
}
void update(int ll,int rr,int c,int l,int r,int rt)
{
    if (ll <= l && r <= rr)
    {
        sum[rt] += c*(r-l+1);
        add[rt] += c;
        return;
    }
    int m = (l+r) >> 1;
    pushdown(rt,m-l+1,r-m);
    if (ll <= m) update(ll,rr,c,l,m,rt << 1);
    if (rr > m) update(ll,rr,c,m+1,r,rt << 1|1);
    pushup(rt);
}
int query(int ll,int rr,int l,int r,int rt)
{
    if (ll <= l && r <= rr)
    {
        return sum[rt];
    }
    int m = (l+r) >> 1;
    pushdown(rt,m-l+1,r-m);
    int ans = 0;
    if (ll <= m) ans += query(ll,rr,l,m,rt << 1);
    if (rr > m) ans += query(ll,rr,m+1,r,rt << 1|1);
    return ans;
}
int main()
{
    scanf("%d%d%d",&n,&k,&q);
    build(1,u,1);
    for (int i = 0;i < n;i++)
    {
        int a,b;
        scanf("%d%d",&a,&b);
        update(a,b,1,1,u,1);
    }
    for (int i = 1;i <= u;i++)
    {
        a[i] = query(i,i,1,u,1);
    }
    build2(1,u,1);
    for (int i = 0;i < q;i++)
    {
        ans  = 0;
        int a,b;
        scanf("%d%d",&a,&b);
        query2(a,b,1,u,1);
        printf("%d\n",ans);
    }
    return 0;
}

C. Karen and Game
题意：
一个游戏，每次可以对一行上的所有数加1或者对每一列上的数加1，现在给出结果矩阵，问最少多少次操作可以把结果矩阵得出来。
思路：
找每一行的最小值，如果不是0，就把这行的每个数减去这个最小值，然后每一列也这么干。
第一次wa，是因为找的不是最小次数。
试想
1 1 1
1 1 1
1 1 1
1 1 1
这个矩阵，如果说先横着来的话，那么答案是4，但是答案是3，所以后来改进，先横后竖，先竖后横，两种的次数比较一下就可以了，中间的操作用队列记录一下。
代码：

#include <stdio.h>
#include <string.h>
#include <queue>
using namespace std;
int a[105][105];
int w[105][105];
typedef pair<char,int> p;
queue<p> q1;
queue<int> qq1;
queue<p> q2;
queue<int> qq2;
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]);
        w[i][j] = a[i][j];
    }
    bool f = 0;
    int ans1 = 0;
    for (int i = 1;i <= n;i++)
    {
        int minn = 600;
        for (int j = 1;j <= m;j++)
        {
            if (minn > a[i][j]) minn = a[i][j];
        }
        if (minn >= 1)
        {
            qq1.push(minn);
            ans1 += minn;
            q1.push(p('r',i));
            for (int j = 1;j <= m;j++)
                a[i][j] -= minn;
        }
    }
    for (int i = 1;i <= m;i++)
    {
        int minn = 600;
        for (int j = 1;j <= n;j++)
        {
            if (a[j][i] < minn) minn = a[j][i];
        }
        if (minn >= 1)
        {
            qq1.push(minn);
            ans1 += minn;
            q1.push(p('c',i));
            for (int j = 1;j <= n;j++)
                a[j][i] -= minn;
        }
    }
    int ans2 = 0;
    for (int i = 1;i <= m;i++)
    {
        int minn = 600;
        for (int j = 1;j <= n;j++)
        {
            if (w[j][i] < minn) minn = w[j][i];
        }
        if (minn >= 1)
        {
            qq2.push(minn);
            ans2 += minn;
            q2.push(p('c',i));
            for (int j = 1;j <= n;j++)
                w[j][i] -= minn;
        }
    }
    for (int i = 1;i <= n;i++)
    {
        int minn = 600;
        for (int j = 1;j <= m;j++)
        {
            if (minn > w[i][j]) minn = w[i][j];
        }
        if (minn >= 1)
        {
            qq2.push(minn);
            ans2 += minn;
            q2.push(p('r',i));
            for (int j = 1;j <= m;j++)
                w[i][j] -= minn;
        }
    }
    for (int i = 1;i <= n;i++)
        for (int j = 1;j <= m;j++)
    {
        if (a[i][j] != 0) f = 1;
    }
    if (f) printf("-1\n");
    else
    {
        if (ans1 > ans2)
        {
            printf("%d\n",ans2);
            while (!q2.empty())
            {
                p t = q2.front();q2.pop();
                int ti = qq2.front();qq2.pop();
                char c = t.first;
                int po = t.second;
                if (c == 'r')
                {
                    for (int i = 1;i <= ti;i++)
                        printf("row %d\n",po);
                }
                if (c == 'c')
                {
                    for (int i = 1;i <= ti;i++)
                        printf("col %d\n",po);
                }
            }
        }
        else
        {
            printf("%d\n",ans1);
            while (!q1.empty())
            {
                p t = q1.front();q1.pop();
                int ti = qq1.front();qq1.pop();
                char c = t.first;
                int po = t.second;
                if (c == 'r')
                {
                    for (int i = 1;i <= ti;i++)
                        printf("row %d\n",po);
                }
                if (c == 'c')
                {
                    for (int i = 1;i <= ti;i++)
                        printf("col %d\n",po);
                }
            }
        }
    }
    return 0;
}