DQS DQS

HIT Summer Training Day5 单调栈|单调队列|堆|st表|并查集

in 栈|队列|堆,st表,算法,并查集,数据结构,模拟赛read (177) 文章转载请注明来源!

单调队列和单调栈的姿势还需要提高。以后要多练习一下带权并查集。


A : hdu - 1870

栈维护现在外面有几个左括号,碰到一个右括号就弹出。

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<stack>
using namespace std;

const int SZ = 200000;


stack<char> S;

char a[SZ];

int get_ans(char s[])
{
    int n = strlen(s);
    int ans = 0;
    for(int i = 0;i < n;i ++)
    {
        if(s[i] == '(') S.push(s[i]),ans ++;
        else if(s[i] == 'B') return ans;
        else S.pop(),ans --;
    }
    return ans;
}

int main()
{
    while(~scanf("%s",a))
    {
        printf("%d\n",get_ans(a));
    }
    return 0;
}


B : hdu - 1022

给一个序列,问能否通过多次进出栈操作使其变为另一个序列。

模拟一下,若当前栈头和另一个序列对应点相同则弹出。

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<stack>
using namespace std;

const int SZ = 5000000;


stack<char> S;

char a[SZ],b[SZ];
int n,opt[SZ];

bool check()
{
    while(S.size()) S.pop();
    int j = 0,t = 0;
    for(int i = 0;i < n && j < n;i ++)
    {
        S.push(a[i]);
        opt[++ t] = 1;
        while(S.size() && j < n&& S.top() == b[j])
            S.pop(),opt[++ t] = 0,j ++;
    }
    while(S.size() && j < n && S.top() == b[j])
        S.pop(),opt[++ t] = 0,j ++;
    if(S.size() || t < 2 * n)
        return false;
    return true;
}

int main()
{
    while(~scanf("%d%s%s",&n,a,b))
    {
        if(!check()) puts("No.");
        else
        {
            puts("Yes.");
            for(int i = 1;i <= 2 * n;i ++)
                if(opt[i] == 0) puts("out");
                else puts("in");
        }
        puts("FINISH");
    }
    return 0;
}


C : hdu - 1237

先中缀转后缀,再模拟。

中缀转后缀:

遇到数则加入后缀表达式中,遇到符号则考虑将其入栈:若栈为空或者当前元素优先级比栈顶元素优先级高,则入栈,否则一直弾栈到后缀表达式中,直到栈为空或者当前元素优先级比栈顶元素优先级高时停止。最终将栈内元素弹出加入后缀表达式中。

计算:

遇到数字就入栈。遇到符号,弹出两个数字计算然后入栈。最终栈顶元素就是答案。

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<stack>
using namespace std;

typedef long long LL;
const int SZ = 200000;

LL read()
{
    char a = getchar();
    LL n = 0; bool flag = 0;
    while(a > '9' || a < '0') { if(a == '-') flag = 1; a = getchar(); }
    while(a <= '9' && a >= '0') n = n * 10 + a - '0',a = getchar();
    if(flag) n = -n;
    return n;
}

bool isnum(char c) { return '0' <= c && c <= '9'; }
int mp(char x)
{
    if(x == '+' || x == '-') return 1;
    return 2;
}

int mpp(char x)
{
    if(x == '+') return -1;
    if(x == '-') return -2;
    if(x == '*') return -3;
    if(x == '/') return -4;
}

double calc(double x,double y,int c)
{
    if(c == -1) return x + y;
    if(c == -2) return x - y;
    if(c == -3) return x * y;
    if(c == -4) return x / y;
}


int n,m;
double gs[SZ];
char s[SZ];
stack<double> num;
stack<int> S;
stack<char> opt;

double get_num(int l,int r)
{
    double n = 0;
    for(int i = l;i <= r;i ++)
        n = n * 10 + s[i] - '0';
    return n;
}

int change()
{
    int n = strlen(s),l = 0,t = 0;
    for(int i = 0;i < n;i ++)
    {
        if(s[i] == ' ')
        {
            if(!isnum(s[i - 1]))
            {
                if(opt.empty()) opt.push(s[i - 1]);
                else
                {
                    char x = opt.top(),y = s[i - 1];
                    if(mp(y) > mp(x))
                        opt.push(y);
                    else
                    {
                        while(opt.size() && mp(y) <= mp(opt.top())) gs[++ t] = mpp(opt.top()),opt.pop();
                        opt.push(y);
                    }
                }
            }
            else
            {
                gs[++ t] = get_num(l,i - 1);
            }
            l = i + 1;
        }
    }
    gs[++ t] = get_num(l,n - 1);
    while(opt.size()) gs[++ t] = mpp(opt.top()),opt.pop();
    return t;
}

double get_ans(int n)
{
//    for(int i = 1;i <= n;i ++)    printf("%d ",gs[i]); puts("");
    for(int i = 1;i <= n;i ++)
    {
        if(gs[i] >= 0)
            num.push(gs[i]);
        else
        {
            double a = num.top(); num.pop();
            double b = num.top(); num.pop();
//            cout << b << " " << a << " " << gs[i] << " " << calc(b,a,gs[i]) << endl;
            num.push(calc(b,a,gs[i]));
        }
    }
    return num.top();
}


int main()
{
    while(gets(s))
    {
        if(strlen(s) == 1 && s[0] == '0') break;
        while(num.size()) num.pop();
        while(opt.size()) opt.pop();
        while(S.size()) S.pop();
        int len = change();
        printf("%.2f\n",get_ans(len));
    }
    return 0;
}


D : hdu - 3415

给一个长度为n的环状序列,要求区间长度小于等于k的最大区间和。多组答案优先输出左端点靠左的,相同则输出长度最短的。

求个前缀和,答案变成询问对于每个i的$sum[i]-sum[j]$的最大值,即要求$sum[j]$最小。

维护一个单调递增的单调队列,注意弹出左边不合法元素。

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;

typedef long long LL;
const int SZ = 200010;
const int INF = 1000000010;

LL read()
{
    char a = getchar();
    LL n = 0; bool flag = 0;
    while(a > '9' || a < '0') { if(a == '-') flag = 1; a = getchar(); }
    while(a <= '9' && a >= '0') n = n * 10 + a - '0',a = getchar();
    if(flag) n = -n;
    return n;
}

int n,m,a[SZ],sum[SZ];

struct haha
{
    int v,id;
};

deque<haha> q;

int main()
{
    int T;
    scanf("%d",&T);
    while(T --)
    {
        sum[0] = 0;
        scanf("%d%d",&n,&m);
        for(int i = 1;i <= n;i ++)
            scanf("%d",&a[i]),a[i + n] = a[i];
        for(int i = 1;i <= 2 * n;i ++)
            sum[i] = a[i] + sum[i - 1];
        int ans = -INF,L = 0,R = 0;
        q.clear();
        //q.push_front((haha){0,0});
        for(int i = 1;i <= n * 2;i ++)
        {
            while(q.size() && sum[i - 1] < q.front().v) q.pop_front();
            q.push_front((haha){sum[i - 1],i - 1});
            while(q.size() && i - q.back().id > m) q.pop_back();

            int l = q.back().id + 1,r = i,now = sum[i] - q.back().v;
            //if(q.size() == 1) continue;
            if(now > ans)
                ans = now,L = l,R = r;
        //    cout << L << " " << R << endl;
        }
        if(R > n) R -= n;
        printf("%d %d %d\n",ans,L,R);
    }
    return 0;
}
/*
1
6 6
-1 -1 -1 -1 -1 -1
*/


E : hdu - 3530

题意:给n个数,一个区间的权值为这个区间的最大值-最小值。求问满足权值在[L,R]中的最长的区间长度是多少。

网上全是单调队列做法,明明二分更显然……
容易想到二分:二分考虑R,对于L写特判。但细节处理不好(比如可能无解)。
可以二分两次:二分一个小于等于R的最大的答案ansR,大于等于L的最小答案ansL。如果ansR<ansL则无解,否则答案是ansR。

对于单调队列:考虑维护一个单增的单调队列、一个单减的单调队列。统计答案时,如果最大值-最小值比R要大,说明要缩小区间,于是就把元素丢掉。pop时记录上一次丢掉的元素的坐标last,那么当前合法区间就是[last+1,i],可以更新答案。

单调队列做法:

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
using namespace std;

typedef long long LL;
const int SZ = 200010;
const int INF = 1000000010;

LL read()
{
    char a = getchar();
    LL n = 0; bool flag = 0;
    while(a > '9' || a < '0') { if(a == '-') flag = 1; a = getchar(); }
    while(a <= '9' && a >= '0') n = n * 10 + a - '0',a = getchar();
    if(flag) n = -n;
    return n;
}

int n,L,R,a[SZ];

deque<int> q1,q2;

int work()
{
    while(q1.size()) q1.pop_front(); //增
    while(q2.size()) q2.pop_front(); //减
    int last = 0,ans = 0;

    for(int i = 1;i <= n;i ++)
    {
        while(q1.size() && a[q1.back()] >= a[i])
            q1.pop_back();
        while(q2.size() && a[q2.back()] <= a[i])
            q2.pop_back();
        q1.push_back(i),q2.push_back(i);
        while(q1.size() && q2.size() && a[q2.front()] - a[q1.front()] > R)
        {
            if(q1.front() < q2.front()) last = q1.front(),q1.pop_front();
            else last = q2.front(),q2.pop_front();
        }
        if(a[q2.front()] - a[q1.front()] >= L)
            ans = max(ans,i - last);
    }
    return ans;
}

int main()
{
    while(~scanf("%d%d%d",&n,&L,&R))
    {
        for(int i = 1;i <= n;i ++)
            scanf("%d",&a[i]);
        printf("%d\n",work());
    }
    return 0;
}
/*
5 1 7
1 9 1 9 2

*/

二分做法:

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;

typedef long long LL;
const int SZ = 200010;
const int INF = 1000000010;

LL read()
{
    char a = getchar();
    LL n = 0; bool flag = 0;
    while(a > '9' || a < '0') { if(a == '-') flag = 1; a = getchar(); }
    while(a <= '9' && a >= '0') n = n * 10 + a - '0',a = getchar();
    if(flag) n = -n;
    return n;
}

int n,L,R,a[SZ];

int stx[SZ][22],stn[SZ][22];

void get_st()
{
    for(int i = 1;i <= n;i ++)
        stx[i][0] = stn[i][0] = a[i];
    for(int j = 1;j <= log2(n);j ++)
        for(int i = 1;i <= n;i ++)
            stx[i][j] = max(stx[i][j - 1],stx[i + (1 << (j - 1))][j - 1]),
            stn[i][j] = min(stn[i][j - 1],stn[i + (1 << (j - 1))][j - 1]);
}

int ask(int l,int r)
{
    int k = log2(r - l + 1);
    int maxn = max(stx[l][k],stx[r - (1 << k) + 1][k]);
    int minn = min(stn[l][k],stn[r - (1 << k) + 1][k]);
    return maxn - minn;
}

bool checkR(int mid)
{
    for(int i = 1;i <= n - mid + 1;i ++)
    {
        int l = i,r = i + mid - 1;
        int d = ask(l,r);
        if(d <= R) return true;
    }
    return false;
}

int divR()
{
    int l = 1,r = n + 1;
    while(r - l > 1)
    {
        int mid = l + r >> 1;
        if(checkR(mid)) l = mid;
        else r = mid;
    }
    return l;
}



bool checkL(int mid)
{
    for(int i = 1;i <= n - mid + 1;i ++)
    {
        int l = i,r = i + mid - 1;
        int d = ask(l,r);
        if(d >= L) return true;
    }
    return false;
}

int divL()
{
    int l = 0,r = n;
    while(r - l > 1)
    {
        int mid = l + r >> 1;
        if(checkL(mid)) r = mid;
        else l = mid;
    }
    return r;
}

int main()
{
    while(~scanf("%d%d%d",&n,&L,&R))
    {
        for(int i = 1;i <= n;i ++)
            scanf("%d",&a[i]);
        get_st();
        int ansR = divR(),ansL = divL();
        if(ansL > ansR) puts("0");
        else printf("%d\n",ansR);
    }
    return 0;
}
/*
5 1 7
1 9 1 9 2

*/


F : hdu - 1873

堆练习

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;

const int SZ = 200000;

struct haha
{
    int v,id;
};

bool operator <(haha a,haha b)
{
    if(a.v != b.v) return a.v < b.v;
    return a.id > b.id;
}
int n;
priority_queue<haha> q[5];

int main()
{
    while(~scanf("%d",&n))
    {
        for(int i = 1;i <= 3;i ++)
            while(q[i].size()) q[i].pop();
        for(int i = 1,j = 0;i <= n;i ++)
        {
            char s[5];
            scanf("%s",s);
            if(s[0] == 'I')
            {
                int a,b;
                scanf("%d%d",&a,&b);
                q[a].push((haha){b,++ j});
            }
            else
            {
                int x;
                scanf("%d",&x);
                if(q[x].empty()) puts("EMPTY");
                else printf("%d\n",q[x].top().id),q[x].pop();
            }
        }
    }
    return 0;
}


G : hdu - 5884

给一个序列,合并k个值的花费是k个值之和,得到的新的值是这k个值之和。现在给定一个最多花费T,一次合并最多合并x个元素,求最大的x使得将序列合并成一个数的花费小于等于T。

相当于合并果子,只不过一次合并k个数。其实是k叉哈夫曼树。

因为有可能合并时会有一次操作使得合并的数目小于k,要想花费最小必须先合并这些,然后每k个合并一次直到结束。

容易想到可以二分答案然后用上述方法验证。

这个题丧心病狂卡O(nlog^2n),需要用到O(n)的合并果子做法。容易发现若初始的元素递增,那么每次合并后得到的值也是单增的,所以合并后的值可以放到一个队列里,这样就类似于归并排序。

复杂度O(nlogn)

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<map>
using namespace std;

typedef long long LL;
const int SZ = 3000010;
const int INF = 1000000010;

LL read()
{
    LL n = 0;
    char a = getchar();
    int flag = 0;
    while(a < '0' || a > '9') { if(a == '-') flag = 1; a = getchar(); }
    while(a >= '0' && a <= '9') n = n * 10 + a - '0',a = getchar();
    if(flag) n = -n;
    return n;
}


LL a[SZ],tmp[SZ],k;
int l,r,p,n;

LL get_min()
{
    if(l > r) return a[p ++];
    if(p > n) return tmp[l ++];
    return tmp[l] < a[p] ? tmp[l ++] : a[p ++];
}

LL merge(int mid)
{
    l = 1,r = 0,p = 1;
    LL ans = 0;
    if((n - 1) % (mid - 1))
    {
        LL d = 0;
        for(int j = 1;j <= (n - 1) % (mid - 1) + 1;j ++)
            d += get_min();
        tmp[++ r] = d,ans += d;
    }
    for(int j = 1;j <= (n - 1) / (mid - 1);j ++)
    {
        LL d = 0;
        for(int j = 1;j <= mid;j ++)
            d += get_min();
        tmp[++ r] = d;
        ans += d;
    }
    return ans;
}

LL div()
{
    int l = 1,r = n;
    while(r - l > 1)
    {
        int mid = l + r >> 1;
        if(merge(mid) <= k) r = mid;
        else l = mid;
    }
    return r;
}

int main()
{
    int T = read();
    while(T --)
    {
        n = read(),k = read();
        for(int i = 1;i <= n;i ++)
            a[i] = read();
        sort(a + 1,a + 1 + n);
        printf("%lld\n",div());
    }
    return 0;
}

H : hdu - 1213

n个点,m条边,问有多少个联通块。

可以计算有多少个并查集的根节点来计算联通块个数。

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<stack>
using namespace std;

const int SZ = 200000;


stack<char> S;

char a[SZ];

int n,m,fa[SZ];

int find(int x)
{
    return x == fa[x] ? x : fa[x] = find(fa[x]);
}


int main()
{
    int T;
    scanf("%d",&T);
    while(T --)
    {
        scanf("%d%d",&n,&m);
        for(int i = 1;i <= n;i ++) fa[i] = i;
        for(int i = 1;i <= m;i ++)
        {
            int a,b;
            scanf("%d%d",&a,&b);
            int x = find(a),y = find(b);
            fa[x] = y;
        }
        int ans = 0;
        for(int i = 1;i <= n;i ++)
            if(find(i) == i)
                ans ++;
        printf("%d\n",ans);
    }
    return 0;
}


I : hdu - 1829

有许多虫子要嘿嘿嘿,给出一些嘿嘿嘿的关系,问其中有没有虫子是gay。

扩展域并查集。每次嘿嘿嘿就合并u的男的与v的女的、u的女的与v的男的。判断的话就看看u的男的和v的男、u的女的和v的女的的是否是同一个集合即可。

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<stack>
using namespace std;

const int SZ = 1000010;

int n,m,fa[SZ * 2],a[SZ],b[SZ];

int find(int x)
{
    return x == fa[x] ? x : fa[x] = find(fa[x]);
}

bool check()
{
    for(int i = 1;i <= m;i ++)
    {
        int x1 = find(a[i]),y1 = find(b[i]);
        int x2 = find(a[i] + n),y2 = find(b[i] + n);
        if(x1 == y1)
            return false;
        fa[x1] = y2; fa[x2] = y1;
    }
    return true;
}


int main()
{
    int T;
    scanf("%d",&T);
    for(int Case = 1;Case <= T;Case ++)
    {
        scanf("%d%d",&n,&m);
        for(int i = 1;i <= 2 * n;i ++) fa[i] = i;
        for(int i = 1;i <= m;i ++)
            scanf("%d%d",&a[i],&b[i]);
        if(check()) printf("Scenario #%d:\nNo suspicious bugs found!\n",Case);
        else printf("Scenario #%d:\nSuspicious bugs found!\n",Case);
        puts("");
    }
    return 0;
}


J : hdu - 3038

有一个未知的序列,给出许多形如“[l,r]的区间和为k”的条件,问有多少个条件是不合法的。

可以转化成"sum[r]-sum[l-1]=k"。
我们发现,判定一个条件不合法,一定要确定这个区间之和是多少,即其被分割成的各个小区间之和一定都知道了。

对于每个条件,把r和l-1合并,那么对于每次查询,查询l和r是否在同一个区间,就能知道当前区间和是否已经确定了。

并查集中每个点表示其到根节点的距离是多少。我们在这里设父节点一定在子节点左边。

对于每个条件,如果r和l-1不在一个集合,那么尝试合并,合并时将r所在集合的根节点的权值更新。
如果在一个集合,那么两者权值之差就是当前区间的权值和,判断一下即可。

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<map>
using namespace std;

typedef long long LL;
const int SZ = 1000010;
const int INF = 1000000010;

LL read()
{
    LL n = 0;
    char a = getchar();
    int flag = 0;
    while(a < '0' || a > '9') { if(a == '-') flag = 1; a = getchar(); }
    while(a >= '0' && a <= '9') n = n * 10 + a - '0',a = getchar();
    if(flag) n = -n;
    return n;
}

int d[SZ],l[SZ],r[SZ],n,m,fa[SZ],val[SZ];

int find(int x)
{
    if(x == fa[x]) return x;
    int f = find(fa[x]);
    val[x] += val[fa[x]];
    return fa[x] = f;
}

bool check()
{

    return true;
}

int main()
{
    while(~scanf("%d%d",&n,&m))
    {
        for(int i = 0;i <= n;i ++) fa[i] = i,val[i] = 0;
        for(int i = 1;i <= m;i ++)
            l[i] = read() - 1,r[i] = read(),d[i] = read();
        int ans = 0;
        for(int i = 1;i <= m;i ++)
        {
            int u = l[i],v = r[i],dd = d[i];
            int x = find(u),y = find(v);
            if(x != y)
            {
                fa[y] = x;
                val[y] = dd - val[v] + val[u];
            }
            else if(val[v] - val[u] != dd)
                ans ++;
        }
        printf("%d\n",ans);
    }
    return 0;
}

K :codeforces - 279C

给出一个序列,多次询问一个区间内的值是否符合$a_l<=a_{l+1}<=...<=a_{k-1}<=a_k>=a_{k+1}>=...>=a_{r-1}>=a_r$的形式。

我用的是dp的做法…

f1[i]表示i向左递增的拐点下标,f2[i]表示i向右递增的拐点下标。之后就比较一下f1[r]和f2[l]即可。

注意有可能区间最大值有多个,所以需要满足f1[r]<=f2[l]即可。

RMQ做法:预处理f1[i]为i开始递减到最左的下标,f2[i]为i开始递减到最右的下标,然后用RMQ得到区间最大值以及下标,然后判断一下最大值开始向两边拓展是否完全包含询问区间。

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<stack>
using namespace std;

const int SZ = 1000010;
const int INF = 1000000010;

int f1[SZ],f2[SZ],n,m,a[SZ]; //f1:1->i降 f2::i->n升

int main()
{
    scanf("%d%d",&n,&m);
    for(int i = 1;i <= n;i ++)
        scanf("%d",&a[i]);
    a[0] = -INF,a[n + 1] = -INF;
    for(int i = 1;i <= n;i ++)
    {
        f1[i] = i;
        if(a[i] <= a[i - 1]) f1[i] = f1[i - 1];
    }
    for(int i = n;i >= 1;i --)
    {
        f2[i] = i;
        if(a[i] <= a[i + 1]) f2[i] = f2[i + 1];
    }
    //for(int i = 1;i <= n;i ++)   printf("%d ",f1[i]); puts("");
    //for(int i = 1;i <= n;i ++)   printf("%d ",f2[i]); puts("");
    for(int i = 1;i <= m;i ++)
    {
        int l,r;
        scanf("%d%d",&l,&r);
        if(f1[r] <= f2[l] || f1[r] <= l || f2[l] >= r)
            printf("Yes\n");
        else
            printf("No\n");
    }
    return 0;
}


L : hdu - 2888

给一个矩阵,每次询问一个子矩阵的最大值和它是否在四个角上。

二维ST表:$st[x][y][i][j]$为 <x,y> 这个点x向后$2^i$次,y向后$2^j$的最大值。

询问和预处理都是和一维差不多,因为二维所以是四个矩阵取max。

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;

typedef long long LL;
const int SZ = 305;
const int INF = 1000010ll;

int a[SZ][SZ];
int n,m;
int st[SZ][SZ][9][9];

void get_st()
{
    memset(st,0,sizeof(st));
    for(int i = 1;i <= n;i ++)
        for(int j = 1;j <= m;j ++)
            st[i][j][0][0] = a[i][j];

    for(int l = 1;(1 << l) <= m;l ++)
        for(int i = 1;i <= n;i ++)
            for(int j = 1;j <= m - (1 << (l - 1));j ++)
                st[i][j][0][l] = max(st[i][j][0][l - 1],st[i][j + (1 << (l - 1))][0][l - 1]);

    for(int k = 1;(1 << k) <= n;k ++)
        for(int i = 1;i <= n - (1 << (k - 1));i ++)
            for(int j = 1;j <= m;j ++)
                st[i][j][k][0] = max(st[i][j][k - 1][0],st[i + (1 << (k - 1))][j][k - 1][0]);

    for(int k = 1;(1 << k) <= n;k ++)
        for(int l = 1;(1 << l) <= m;l ++)
            for(int i = 1;i <= n - (1 << (k - 1));i ++)
                for(int j = 1;j <= m - (1 << (l - 1));j ++)
                    st[i][j][k][l] = max(max(st[i][j][k - 1][l - 1],st[i + (1 << (k - 1))][j][k - 1][l - 1]),
                                         max(st[i][j + (1 << (l - 1))][k - 1][l - 1],st[i + (1 << (k - 1))][j + (1 << (l - 1))][k - 1][l - 1]));
}

int ask_max(int x1,int y1,int x2,int y2)
{
    int k = log2(x2 - x1 + 1),l = log2(y2 - y1 + 1);
    int ans1 = max(st[x1][y1][k][l],st[x1][y2 - (1 << l) + 1][k][l]);
    int ans2 = max(st[x2 - (1 << k) + 1][y1][k][l],st[x2 - (1 << k) + 1][y2 - (1 << l) + 1][k][l]);
    return max(ans1,ans2);
}

LL read()
{
    char a = getchar();
    LL n = 0; bool flag = 0;
    while(a > '9' || a < '0') { if(a == '-') flag = 1; a = getchar(); }
    while(a <= '9' && a >= '0') n = n * 10 + a - '0',a = getchar();
    if(flag) n = -n;
    return n;
}

int main()
{
    while(~scanf("%d%d",&n,&m))
    {
        for(int i = 1;i <= n;i ++)
            for(int j = 1;j <= m;j ++)
                a[i][j] = read();
        get_st();
        int q = read();
        while(q --)
        {
            int x1 = read(),y1 = read(),x2 = read(),y2 = read();
            //scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
            int ans = ask_max(x1,y1,x2,y2);
            bool flag = 0;
            if(ans == a[x1][y1] || ans == a[x1][y2] || ans == a[x2][y1] || ans == a[x2][y2])
                flag = 1;
            printf("%d %s\n",ans,flag ? "yes" : "no");
        }
    }
    return 0;
}

jrotty WeChat Pay

微信打赏

jrotty Alipay

支付宝打赏

文章二维码

扫描二维码,在手机上阅读!

发表新评论
博客已萌萌哒运行
© 2018 由 Typecho 强力驱动.Theme by Yodu
前篇 后篇
雷姆
拉姆