精华内容
下载资源
问答
  • 题意:找从[l,r]每一个元素都不重复且最大值为r-l+1的区间数 题解:先找到以i为左端点的最远右端点r,然后rmq判断一下最大值是不是r-l+1思路 rmq直接套板子就可以 #include <bits/stdc++.h> using ...

    题意:找从[l,r]每一个元素都不重复且最大值为r-l+1的区间数

    题解:先找到以i为左端点的最远右端点r,然后rmq判断一下最大值是不是r-l+1思路

    rmq直接套板子就可以

    #include <bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    const int maxn = 1e6+10, INF = 0x3f3f3f3f;
    #define pi acos(-1.0)
    int a[maxn],d[maxn][25];
    int vis[maxn],mx[maxn];
    int n;
    void init()
    {
        for(int i=1;i<=n;i++)
            d[i][0]=a[i];
        for(int j=1;(1<<j)<=n;j++)
            for(int i=1;i+(1<<j)-1<=n;i++)
                d[i][j]=max(d[i][j-1],d[i+(1<<j-1)][j-1]);
    }
    int rmq(int l,int r)
    {
        int k=log2(r-l+1);
        return max(d[l][k],d[r-(1<<k)+1][k]);
    }
    
    int main() {
        scanf("%d",&n);
        for(int i=1;i<=n;i++){
            scanf("%d",&a[i]);
        }
        mx[n+1]=n;
        for(int i=n;i>=1;i--){
            if(vis[a[i]])mx[i]=min(mx[i+1],vis[a[i]]-1);
            else mx[i]=mx[i+1];
            vis[a[i]]=i;
        }
        init();
        int ans=0;
        for(int i=1;i<=n;i++){
            int j=i;
            while(j<=mx[i]){
                if(rmq(i,j)==j-i+1){
                    ans++;
                    j++;
                }else j=i+rmq(i,j)-1;
            }
        }
        cout<<ans<<endl;
    }

     

    展开全文
  • Problem G Time Limit : 15000/5000ms (Java/Other) Memory Limit : 65536/32768K (Java/Other) Total Submission(s) : 66 Accepted Submission(s) : 17 Problem Description Mery has a beautiful necklace

    Problem G

    Time Limit : 15000/5000ms (Java/Other)   Memory Limit : 65536/32768K (Java/Other)
    Total Submission(s) : 66   Accepted Submission(s) : 17
    Problem Description
    Mery has a beautiful necklace. The necklace is made up of N magic balls. Each ball has a beautiful value. The balls with the same beautiful value look the same, so if two or more balls have the same beautiful value, we just count it once. We define the beautiful value of some interval [x,y] as F(x,y). F(x,y) is calculated as the sum of the beautiful value from the xth ball to the yth ball and the same value is ONLY COUNTED ONCE. For example, if the necklace is 1 1 1 2 3 1, we have F(1,3)=1, F(2,4)=3, F(2,6)=6.

    Now Mery thinks the necklace is too long. She plans to take some continuous part of the necklace to build a new one. She wants to know each of the beautiful value of M continuous parts of the necklace. She will give you M intervals [L,R] (1<=L<=R<=N) and you must tell her F(L,R) of them.
     

    Input
    The first line is T(T<=10), representing the number of test cases. For each case, the first line is a number N,1 <=N <=50000, indicating the number of the magic balls. The second line contains N non-negative integer numbers not greater 1000000, representing the beautiful value of the N balls. The third line has a number M, 1 <=M <=200000, meaning the nunber of the queries. Each of the next M lines contains L and R, the query.
     

    Output
    For each query, output a line contains an integer number, representing the result of the query.
     

    Sample Input
    2 6 1 2 3 4 3 5 3 1 2 3 5 2 6 6 1 1 1 2 3 5 3 1 1 2 4 3 5
     

    Sample Output
    3 7 14 1 3 6
     
     
    #include<iostream> #include<cstring> #include<string> #include<cstdio> #include<cmath> #include<algorithm> #include<iomanip> using namespace std; #define inf 50050 int v[1000010],b[50050]; long long ans[200005],c[50100];//注意c是long long struct node {     int l,r,id; }; node a[200005]; bool cmp(node a,node b) {     if(a.r==b.r)         return a.l<b.l;     return a.r<b.r; } int lowbit(int x) {     return x&(-x); } long long sum(int x) {     long long res=0;     while(x>0)     {         res+=c[x];         x-=lowbit(x);     }     return res; } void add(int x,int num) {     while(x<=inf)     {         c[x]+=num;         x+=lowbit(x);     } } int main() {     int t,n,m,i;     scanf("%d",&t);     while(t--)     {         scanf("%d",&n);         for(i=1;i<=n;i++)         scanf("%d",&b[i]);         memset(c,0,sizeof(c));         memset(v,0,sizeof(v));         scanf("%d",&m);         for(i=1;i<=m;i++)         {             scanf("%d%d",&a[i].l,&a[i].r);             //if(a[i].l>a[i].r)                 //swap(a[i].l,a[i].r);             a[i].id=i;         }         sort(a+1,a+1+m,cmp);         int rr=1;//当前元素的坐标;         for(i=1;i<=m;i++)         {              while(rr<=a[i].r)             {                 if(v[b[rr]])//v记录元素出现的下标相同元素最后一次出现的位置                     add(v[b[rr]],-b[rr]);                 v[b[rr]]=rr;                 add(v[b[rr]],b[rr]);                 rr++;             }             ans[a[i].id]=sum(a[i].r)-sum(a[i].l-1);         }         for(i=1;i<=m;i++)             printf("%lld\n",ans[i]);             //cout<<ans[i]<<endl;     } }
    展开全文
  • 我文本框中输入 1到50 或更多,保存后 如果输入的数在1到50之间的 则提示已存在,重新输入,请问怎么判断
  • function ran(n,min,max){ var arr=[]; for(i=0;i;i++){ arr[i]=parseInt(Math.random()*(max-min+1)+min); } for(i=0;i;i++){ for(j=i+1;j;j++){ if(arr[i]==arr[j]){ my_ran
    //n 随机几个 min最小范围,max最大范围
    function ran(n,min,max){
      var arr=[];
      for(i=0;i<n;i++){
        arr[i]=parseInt(Math.random()*(max-min+1)+min);
      }
      for(i=0;i<n;i++){
        for(j=i+1;j<n;j++){
          if(arr[i]==arr[j]){
            my_ran(n,min,max);
            return fault;
          }
        }
      }
      document.getElementById("text").value=arr;
    }

    展开全文
  • 区间第k大】 #include using namespace std; const int MAXN = 1e5 + 10; struct node { int ls, rs, sum; } ns[MAXN * 20]; int ct; int rt[MAXN * 20]; void cpy(int& now, int old) { now = ++ct; ...
    #include <bits/stdc++.h>
    using namespace std;
    const int MAXN = 1e5 + 10;
    
    struct node {
    	int ls, rs, sum;
    } ns[MAXN * 20];
    
    int ct;
    int rt[MAXN * 20];
    
    void cpy(int& now, int old) {
    	now = ++ct;
    	ns[now] = ns[old];
    }
    
    void pushUp(int now) {
    	ns[now].sum = ns[ns[now].ls].sum + ns[ns[now].rs].sum;
    }
    
    void build(int& now, int l, int r) {
    	now = ++ct;
    	ns[now].sum = 0;
    	if (l == r) return;
    	int m = (l + r) >> 1;
    	build(ns[now].ls, l, m);
    	build(ns[now].rs, m + 1, r);
    }
    
    int update( int old, int l, int r, int pos,int val) {
    	int now;
    	cpy(now, old);
    	if (l == r) {
    		ns[now].sum+=val;
    		return now;
    	}
    	int m = (l + r) >> 1;
    	if (pos <= m)ns[now].ls = update(ns[old].ls, l, m, pos, val);
    	else ns[now].rs = update(ns[old].rs, m + 1, r, pos, val);
    	pushUp(now);
    	return now;
    }
    
    int query(int l,int r,int now,int pos) {
    	if (l == r) return ns[now].sum;
    	int m = (l + r) >> 1;
    	if (pos <= m) return ns[ns[now].rs].sum + query(l, m, ns[now].ls, pos);
    	return query(m+1,r,ns[now].rs,pos);
    }
    
    void init(int n) {
    	ct = 0;
    	build(rt[0], 1, n);
    }
    
    int a[MAXN], b[MAXN];
    
    int main() {
    	int n, m;
    	while (~scanf("%d",&n)) {
    		for (int i = 1; i <= n; i++) {
    			scanf("%d", &a[i]);
    		}
    		map<int, int>mp;
    		init(n);
    		for (int i = 1; i <= n; i++) {
    	
    			if (!mp[a[i]]) {
    				rt[i] = update(rt[i - 1], 1, n, i, 1);
    			}
    			else {
    				int tmp = update(rt[i - 1], 1, n, mp[a[i]], -1);
    				rt[i] = update(tmp, 1, n, i, 1);
    			}
    			mp[a[i]] = i;
    		}
    		scanf("%d", &m);
    		while (m--) {
    			int s, t;
    			scanf("%d%d", &s, &t);
    			printf("%d\n", query(1, n, rt[t], s));
    		}
    	}
    }
    

    【区间第k大】

    #include <bits/stdc++.h>
    using namespace std;
    const int MAXN = 1e5 + 10;
    
    struct node {
        int ls, rs, sum;
    } ns[MAXN * 20];
    
    int ct;
    int rt[MAXN * 20];
    
    void cpy(int& now, int old) {
        now = ++ct;
        ns[now] = ns[old];
    }
    
    void pushUp(int& now) {
        ns[now].sum = ns[ns[now].ls].sum + ns[ns[now].rs].sum;
    }
    
    void build(int& now, int l, int r) {
        now = ++ct;
        ns[now].sum = 0;
        if (l == r) return;
        int m = (l + r) >> 1;
        build(ns[now].ls, l, m);
        build(ns[now].rs, m + 1, r);
    }
    
    void update(int& now, int old, int l, int r, int x) {
        cpy(now, old);
        if (l == r) {
            ns[now].sum++;
            return;
        }
        int m = (l + r) >> 1;
        if (x <= m) update(ns[now].ls, ns[old].ls, l, m, x);
        else update(ns[now].rs, ns[old].rs, m + 1, r, x);
        pushUp(now);
    }
    
    int query(int s, int t, int l, int r, int k) {
        if (l == r) return l;
        int m = (l + r) >> 1;
        int cnt = ns[ns[t].ls].sum - ns[ns[s].ls].sum;
        //cout << s << " " << t << " " << cnt << endl;
        if (k <= cnt) return query(ns[s].ls, ns[t].ls, l, m, k);
        return query(ns[s].rs, ns[t].rs, m + 1, r, k - cnt);
    }
    
    void init(int n) {
        ct = 0;
        build(rt[0], 1, n);
    }
    
    int a[MAXN], b[MAXN];
    
    int main() {
        //freopen("in.txt", "r", stdin);
        int T;
        scanf("%d", &T);
        while (T--) {
            int n, m;
            scanf("%d%d", &n, &m);
            for (int i = 1; i <= n; i++) {
                scanf("%d", &a[i]);
                b[i] = a[i];
            }
            sort(b + 1, b + n + 1);
            int sz = unique(b + 1, b + 1 + n) - b - 1;
            init(sz);
            for (int i = 1; i <= n; i++) {
                a[i] = lower_bound(b + 1, b + 1 + sz, a[i]) - b;
                update(rt[i], rt[i - 1], 1, sz, a[i]);
            }
            /*for (int i = 0; i <= 5 * n; i++) {
                printf("%d, rt = %d, ls = %d, rs = %d, sum = %d\n", i, rt[i], ns[rt[i]].ls, ns[rt[i]].rs, ns[rt[i]].sum);
            }*/
            while (m--) {
                int s, t, k;
                scanf("%d%d%d", &s, &t, &k);
                printf("%d\n", b[query(rt[s - 1], rt[t], 1, sz, k)]);
            }
        }
        return 0;
    }

     

    展开全文
  • 主席树可以求出来一个区间中出现数字个数,所以先把数字个数求出来,再求由左边界一直到n范围中的第(k+1)/2小即可 #include #define N 200005 using namespace std; typedef long long ll; int T,n,m,cnt,pos,a...
  • 如果知道请看我的另一篇博文: https://blog.csdn.net/flymoyu/article/details/88745867 整体描述: 主席树又称函数式线段树或者可持久化线段树,顾名思义,也就是通过函数来实现的线段树...
  • 这样维护的时候就可以只保留最后一个不重复的数字 */ sort ( node + 1 , node + m + 1 ) ; for ( int i = 1 ; i m ; i ++ ) { for ( int j = node [ i - 1 ] . r + 1 ; j node [ i ] ...
  • 不重复计数的话r边界依次增加则只有某个数最后一次出现时才有意义,这样就可以数状数组维护位置了,如果某个数第二次出现,则第二次的位置加1,第一次出现的位置减1,这样就可以解决这个问题了,注意的是维护位置的...
  • Excel中产生随机数的函数有两个,Rand函数和Randbetween函数Rand函数使用...20),产生的是1-20区间的随机整数如果我们现在想要生成一串数字,它是某个区间不重复的数据例1、生成1-10区间的不重复数据。如果想抽取...
  • 不重复区间 - 线段树

    2018-09-28 16:41:37
    给一个数列,每次修改一个数字或者问有多少区间内没有相同的数字的区间。n,m≤105n,m\le10^5n,m≤105 题解: 首先固定r,相当于l不断变小同时pre的max变大,一直到要max(pre)&gt;=l为止。 考虑类似线段树维护...
  • 只取五分钟区间的一笔资料 2019-01-01 00:04:11 (2019-01-01 00:00:00 ~ 2019-01-01 00:05:00) 2019-01-01 00:08:38 (2019-01-01 00:05:00 ~ 2019-01-01 00:10:00) 无资料 (2019-01-01 00:10:00 ~ 2019-01-01 00:...
  • 通过移位和逻辑运算,快速生成给定区间不重复随机数。 形象地说就是随机打乱值的顺序。 发现网上其它的方法都太慢了,又刚好想到这个方法, 就传上来了。
  • #生成某区间不重复的N个随机数的方法 import random; #1、利用递归生成 resultList=[];#用于存放结果的List A=1; #最小随机数 B=100 #最大随机数 COUNT=5 resultList=random.sample(range(A,B+1),COUNT); print...
  • 解题思路:关键是要先把询问的几个区间先存起来,将其按照区间的右端点从小到大排序,这样当去掉某一区间内的重复值时就不会影响其他区间,因为其他区间的右端点要么比它小,要么比它大,比它小的不会受影响(因为...
  • 问题有这样一种需求,在这样一个数组中...,随机取n个选项且不重复,n随机且在1-m这个范围之内,其中m是个确定的数且m<=数组长度。思路取特定区间的一个随机数// 从区间[1,4]随机取一个数Random random = new...
  • 图解,sql判断两个时间区间交叉重复 这个图里已经说的很清楚了,最...要求两个时间区间或者其他区间不能交叉,但是端点可以相等的情况 2.区间的大小有如下三种情况:(b-a表示传入参数,end - start 表示数据库字段...
  • unity3D C# 在区间内生成不重复的随机数 1、使用哈希表 /// <summary> /// 生成随机数 /// </summary> /// <param name="num">随机数个数</param> /// <param name="min">...
  • sql两个时间区间或者其他区间不能交叉,但是端点可以相等图解 这是自己的总结的图,图里已经说的很清楚了,最下边将图中的问题一并附上,如果要写成sql的自己根据条件和字段名改一下就可以了。 将 a b 慢慢向右移会...
  • 问题 有这样一种需求,在这样一个数组中...,随机取n个选项且不重复,n随机且在1-m这个范围之内,其中m是个确定的数且m<=数组长度。 思路 取特定区间的一个随机数 // 从区间[1,4]随机取一个数 Random random ...
  • JAVA实现指定区间取N个不重复随机数

    千次阅读 2018-03-17 11:15:36
    近日在面试中多次被问到从规定区间取N个随机数... * 功能:产生min-max中的n个不重复的随机数 * * min:产生随机数的其实位置 * mab:产生随机数的最大位置 * n: 所要产生多少个随机数 * */ public static i...
  • [img=https://img-bbs.csdn.net/upload/201608/05/1470362284_373397.jpg][/img] 如图,每次增加的区间不能在已有的区间内。 最好可以在JSP页面做验证
  • 前些天遇到个问题,要实现从 [0,2000] 的数字中读取出100个不重复的随机数,该问题可以有多种实现方法,孤在此例举了一种时间复杂度仅为O[n],空间复杂度为O[n] 的例子,供大家参考: function getRandomArr() { //...
  • JAVA指定区间范围取N个不重复随机整数 private HashSet<Integer> getRandomNum(int n,int range) throws Exception { Random random = new Random(); HashSet<Integer> targetSet = new HashSet<...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 2,151
精华内容 860
关键字:

区间不重复