Chef and Problems(from Code

Stella981
• 阅读 590

题目: 题意:给定序列,求[l,r]区间内数字相同的数的最远距离。

            链接:https://www.codechef.com/problems/QCHEF

Chef and Problems(from Code Chef and Problems(from Code

#include<bits/stdc++.h>
#define LL long long
#define ULL unsigned long long
#define rep(i,j,k) for(int i=j;i<=k;i++)
#define dep(i,j,k) for(int i=k;i>=j;i--)
#define INF 0x3f3f3f3f
#define mem(i,j) memset(i,j,sizeof(i))
#define make(i,j) make_pair(i,j)
#define pb push_back
using namespace std;
const int N=1e5+10;
int a[N],pos[N],mi[N],ma[N],t[N],ans[N],n,m,k,block,tmp;
struct noq {
    int l,r,id;
}q[N];
bool cmp(noq a,noq b) {
    return pos[a.l]==pos[b.l]?a.r<b.r:pos[a.l]<pos[b.l];
}
void add(int x) {
    mi[a[x]]=min(mi[a[x]],x);
    ma[a[x]]=max(ma[a[x]],x);
    tmp=max(tmp,ma[a[x]]-mi[a[x]]);
}
int query(int l,int r) {
    int mx=0;
    rep(j,l,r)
        t[a[j]]=0x3f3f3f3f;
    rep(j,l,r){
        t[a[j]]=min(t[a[j]],j);
        mx=max(mx,j-t[a[j]]);
    }
    return mx;
}
int slove(int qnum,int bnum) {
    int i=qnum; int L=min(bnum*block,n); int l=L+1,r=L;
    mem(ma,-63); mem(mi,63); tmp=0;
    for(;pos[q[i].l]==bnum;i++) {
        if(pos[q[i].l]==pos[q[i].r]) {
            ans[q[i].id]=query(q[i].l,q[i].r); continue;
        }
        while(r<q[i].r) add(++r);
        int mx=0;
        rep(j,q[i].l,l) t[a[j]]=0x3f3f3f3f;
        rep(j,q[i].l,l) {
            t[a[j]]=min(t[a[j]],j);
            mx=max(mx,max(j-t[a[j]],ma[a[j]]-j));
        }
        ans[q[i].id]=max(mx,tmp);
    }
    return i;
}
int main() {
    scanf("%d %d %d",&n,&m,&k); block=sqrt(n);
    rep(i,1,n) {
        scanf("%d",&a[i]); pos[i]=(i-1)/block+1;
    }
    rep(i,1,k) {
        scanf("%d %d",&q[i].l,&q[i].r); q[i].id=i;
    }
    sort(q+1,q+1+k,cmp);
    int up=pos[k]; int p=1;
    rep(i,1,up) p=slove(p,i);
    rep(i,1,k) printf("%d\n",ans[i]);
    return 0;
}

View Code

点赞
收藏
评论区
推荐文章
待兔 待兔
4个月前
手写Java HashMap源码
HashMap的使用教程HashMap的使用教程HashMap的使用教程HashMap的使用教程HashMap的使用教程22
DaLongggggg DaLongggggg
3年前
python-算法训练 区间k大数查询
问题描述给定一个序列,每次询问序列中第l个数到第r个数中第K大的数是哪个。输入格式第一行包含一个数n,表示序列长度。第二行包含n个正整数,表示给定的序列。第三个包含一个正整数m,表示询问个数。接下来m行,每行三个数l,r,K,表示询问序列从左往右第l个数到第r个数中,从大往小第K大的数是哪个。序列元素从1开始标号。输出格式总共输出m行,每行一个数
Stella981 Stella981
3年前
LeetCode 169. 求众数
原文链接: LeetCode169.求众数(https://my.oschina.net/ahaoboy/blog/3118038)https://leetcodecn.com/problems/majorityelement/(https://www.oschina.net/action/GoToLink?urlhttps%3A%2F
Stella981 Stella981
3年前
LeetCode 72. 编辑距离
原文链接: LeetCode72.编辑距离(https://my.oschina.net/ahaoboy/blog/3113850)https://leetcodecn.com/problems/editdistance/(https://www.oschina.net/action/GoToLink?urlhttps%3A%2F%2F
Stella981 Stella981
3年前
Gym102040 .Asia Dhaka Regional Contest(寒假自训第9场)
B.CountingInversion题意:给定L,R,求这个区间的逆序对数之和。(L,R<1e15)思路:一看这个范围就知道是数位DP。只是维护的东西稍微多一点,需要记录后面的各种数字的个数cnt,以及逆序对和sum,以及出现了多少种后缀num。那么枚举到当前位时,假设为i,那
Stella981 Stella981
3年前
Leetcode 239题 滑动窗口最大值(Sliding Window Maximum) Java语言求解
题目链接https://leetcodecn.com/problems/slidingwindowmaximum/(https://www.oschina.net/action/GoToLink?urlhttps%3A%2F%2Fleetcodecn.com%2Fproblems%2Fslidingwindowmaximum%
Stella981 Stella981
3年前
558. Quad Tree Intersection
https://leetcode.com/problems/quadtreeintersection/description/我觉得是用意挺好的一题目。求两个四叉树的逻辑union,可惜测试用例里面居然包含对题目外因素的检查(那个id)懒得弄了。思路其实挺简单,但是很容易忽略一个edgecase,就是当所有children的value都一致
Stella981 Stella981
3年前
851. Loud and Rich —— weekly contest 87
851\.LoudandRich题目链接:https://leetcode.com/problems/loudandrich/description/(https://www.oschina.net/action/GoToLink?urlhttps%3A%2F%2Fleetcode.com%2Fpr
Stella981 Stella981
3年前
LeetCode初级算法之树:98 验证二叉搜索树
01题目信息题目地址:https://leetcodecn.com/problems/validatebinarysearchtree/给定一个二叉树,判断其是否是一个有效的二叉搜索树。假设一个二叉搜索树具有如下特征:节点的左子树只包含小于当前节点的数。
Wesley13 Wesley13
3年前
83. 删除排序链表中的重复元素
题目描述题目地址:https://leetcodecn.com/problems/removeduplicatesfromsortedlist/给定一个排序链表,删除所有重复的元素,使得每个元素只出现一次。示例1:输入:112输出:12示例 2:输入:11233输出: