首页 > 试题广场 >

密码生成

[编程题]密码生成
  • 热度指数：6865 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
小汪作为一个有数学天分的程序猿，设计了一套密码生成器来搞定自己的密码问题。
密码生成器由 N 个槽位组成，槽位的下标为 0~N-1 ，每个槽位存储一个数。起初每个槽位都是 0 。
密码生成器会进行 M 轮计算，每轮计算，小汪会输入两个数 L , R (L<=R),密码生成器会将这两个数作为下标，将两个下标之间（包含）的所有槽位赋值为 i（ i 为当前的轮次， i ∈ [1,M]）。
M轮计算完成后，密码生成器会根据槽位的最终值生成一条密码，密码的生成规则为：
（0*a[0] + 1*a[1] + 2*a[2] + ... + (N-1)*a[N-1]) mod 100000009
其中a[i]表示第i个槽位的最终值。
请帮助小汪把他的密码生成器实现为代码。

数据范围： 
对于前30%的测试数据，保证 N,M<=10000
对于前50%的测试数据，保证 N,M<=200000
对于100%的测试数据，保证 N<=1.5*10^7,M<=200000

输入描述:
第一行为两个整数N,M,表示槽位个数和计算轮数。
接下来M行，每行两个整数Li,Ri，表示第i轮计算的输入。


输出描述:
输出一行，一个整数A,表示小汪的开机密码。
示例1

输入

5 3
2 3
1 2
1 1

输出

10

说明

对于输入样例，密码生成过程如下：

初始：  0 0 0 0 0
第1轮：0 0 1 1 0
第2轮：0 2 2 1 0
第3轮：0 3 2 1 0
密码生成器最终生成 0 3 2 1 0，则密码为(0*0 + 3*1 + 2*2 + 1*3 + 0*4) mod 100000009 = 10

备注:
mod 表示取余操作，a mod b表示a,b相除得到的余数
对于前30%的测试数据，保证 N,M<=10000
对于前50%的测试数据，保证 N,M<=200000
对于100%的测试数据，保证 N<=1.5*10^7,M<=200000
算法知识视频讲解
添加回答
qwesde头像 qwesde
并查集模板题
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <bits/stdc++.h>
#include <cassert>
using namespace std;

const int N = 2e7 + 10, M = 6e6 +10;
const long long mod = 100000009;

int fa[N];
int find(int x)  // 并查集
{
    if (fa[x] != x) fa[x] = find(fa[x]);
    return fa[x];
}
int w[N];

pair<int,int> pi[M];


int main()
{
    int n,m,p,q;
   
    while (~scanf("%d%d", &n,&m))
    {
        // 需要注意，这个模型使用并查集的话，要多初始化一个位置，n+1 否则MLE or TLE
        if (n > N) return 9;
        for (int i = 0;  i <= n + 1; i++) fa[i] = i, w[i] = 0;
        
        int l, r;
        memset(w, 0, sizeof w);
    
        
        for (int i = 0; i < m; i++) {
            int l,r;
            scanf("%d%d", &l, &r);
            l ++; r ++;
            pi[i] = {l, r};
        }
        
        for (int i  = m - 1; i >= 0; i--)
        {
            int l = pi[i].first, r = pi[i].second;
            
            if (l > r) swap(l ,r);
            while (find(l) <= r)
            {
                l = find(l);
                w[l] = i + 1;
                fa[l] = l + 1;
            }
        }
         long long sum = 0;
        for (int i = 1; i <= n; i ++ ) {
            sum = (sum + (1ll * (i - 1) * w[i]) % mod) % mod;
        }
        printf("%lld\n", sum);
    }
    
    
    
    
    return 0;
}
发表于 2021-07-09 12:07:08 回复(0)
游客89i800头像 游客89i800 
public class Main {

    public static void main(String[] args) {

        Scanner scanner = new Scanner(System.in);
        int sum = 0;
        int password;
        int N = scanner.nextInt();
        int M = scanner.nextInt();

        int[] arr = new int[N];
        for (int i=0;i<M;i++){

            int L = scanner.nextInt();
            int R = scanner.nextInt();
            for(int j=L;j<R;j++){
                arr[j] = i+1;
            }
            arr[R] = i+1;

        }

        for (int i=0;i<arr.length;i++){
            sum+= i*arr[i];
        }
        password = sum % 100000009;
        System.out.println(password);
    }

}

发表于 2020-08-11 09:51:21 回复(1)
牛客58028594号头像 牛客58028594号
这阴间用例上来就10000还不分行上哪自测去
发表于 2020-09-02 17:44:54 回复(0)
GoatGirl98头像 GoatGirl98
C++100分代码通过，真的太不容易了

那么本题的正解是采用离散化+线段树
首先区间赋值很容易想到的是线段树，而纯线段树会爆空间，只能拿到50分，如果写动态开点线段树没准会过，先上一个50分代码... 
#include<cstdio>
#include<cstring>
#include<algorithm>
#define Lchild(x) ((x) << 1)
#define Rchild(x) (((x) << 1) + 1)
using namespace std;
typedef long long ll;
const ll MOD = 100000009;
const int maxn = 15000010;
inline void write(ll x) {
    if (x < 0)putchar('-'), x = -x;
    if (x > 9)write(x / 10);
    putchar(x % 10 + 48);
}
inline int read() {
    int k = 0, f = 1;
    char c = getchar();
    while (c < '0' || c>'9') {
        if (c == '-')f = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9') {
        k = (k << 1) + (k << 3) + c - 48;
        c = getchar();
    }
    return k * f;
}
struct op {
    int l, r, c;
}a[maxn];
//[l, r]的区间和
inline ll sum(ll l, ll r) { return (l + r) * (r - l + 1) / 2; }
int n, m;
int x[maxn << 1], x_size, realx_size, c[maxn << 1];
int L, R;
ll ans;
struct SegmentTree {
    struct Node {
        int value, tag_Set;
    }nodes[maxn << 2];
    SegmentTree() {
        memset(nodes, 0, sizeof(nodes));
    }
    inline void pushup(int root) {
        nodes[root].value = nodes[Lchild(root)].value + nodes[Rchild(root)].value;
    }
    inline void build(int root, int l, int r) {
        nodes[root].tag_Set = 0;
        if (l == r)nodes[root].value = 0;
        else {
            int m = (l + r) >> 1;
            build(Lchild(root), l, m);
            build(Rchild(root), m + 1, r);
            pushup(root);
        }
    }
    inline void pushdown(int root, int l, int r) {
        int m = (l + r) >> 1;
        if (nodes[root].tag_Set) {
            nodes[Lchild(root)].tag_Set = nodes[Rchild(root)].tag_Set = nodes[root].tag_Set;
            nodes[Lchild(root)].value = (m - l + 1) * nodes[root].tag_Set;
            nodes[Rchild(root)].value = (r - m) * nodes[root].tag_Set;
            nodes[root].tag_Set = 0;
        }
    }
    inline void updateSet(int root, int curl, int curr, int tarl, int tarr, int k) {
        if (tarr < curl || curr < tarl)return;
        if (tarl <= curl && curr <= tarr) {
            nodes[root].tag_Set = k;
            nodes[root].value = (curr - curl + 1) * k;
            return;
        }
        pushdown(root, curl, curr);
        int m = (curl + curr) >> 1;
        if (tarl <= m) updateSet(Lchild(root), curl, m, tarl, tarr, k);
        if (tarr > m) updateSet(Rchild(root), m + 1, curr, tarl, tarr, k);
        pushup(root);
    }
    inline int query(int root, int curl, int curr, int tarl, int tarr) {
        if (tarr < curl || curr < tarl)return 0;
        if (tarl <= curl && curr <= tarr) {
            return nodes[root].value;
        }
        pushdown(root, curl, curr);
        int m = (curl + curr) >> 1;
        int ret = 0;
        if (tarl <= m) ret += query(Lchild(root), curl, m, tarl, tarr);
        if (tarr > m) ret += query(Rchild(root), m + 1, curr, tarl, tarr);
        return ret;
    }

};
SegmentTree tree;

int main() {
    n = read(), m = read();
    tree.build(1, 1, n);
    for (int i = 1; i <= m; ++i) {
        L = read() + 1, R = read() + 1;
        tree.updateSet(1, 1, n, L, R, i);
    }
    for (int i = 0; i < n; ++i)
        ans = (ans + 1ll * tree.query(1, 1, n, i + 1, i + 1) * i) % MOD;

    write(ans);
}

那么考虑到数据范围，我们需要对区间进行离散化，把所有的端点坐标罗列下来，排序去重
比如说一共4个坐标点
1 4 6 10000000000
我们就可以映射到
1 2 3 4
然后接下来，只需要在赋值的时候直接在离散化的点上操作就可以
但是这样只能拿到20分，还有一个小问题
就是当我们的赋值是在1到4和6到10000000000的时候，就会忽略掉5会怎么样
所以当相邻两个点x和y的差大于1的时候，我们需要将x+1和y-1同时加入离散化的坐标数组，再做一次排序去重

100分代码: 
#include<cstdio>
#include<cstring>
#include<algorithm>
#define Lchild(x) ((x) << 1)
#define Rchild(x) (((x) << 1) + 1)
using namespace std;
typedef long long ll;
const ll MOD = 100000009;
const int maxn = 1000010;
inline void write(ll x) {
    if (x < 0)putchar('-'), x = -x;
    if (x > 9)write(x / 10);
    putchar(x % 10 + 48);
}
inline int read() {
    int k = 0, f = 1;
    char c = getchar();
    while (c < '0' || c>'9') {
        if (c == '-')f = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9') {
        k = (k << 1) + (k << 3) + c - 48;
        c = getchar();
    }
    return k * f;
}
struct op {
    int l, r;
}a[maxn];
//[l, r]的区间和
inline ll sum(ll l, ll r) {return (l + r) * (r - l + 1) / 2;}
int n, m;
int x[maxn << 1], x_size, realx_size, c[maxn << 1];
int L, R;
ll ans;
struct SegmentTree {
    struct Node {
        int value, tag_Set;
    }nodes[maxn << 3];
    SegmentTree() {
        memset(nodes, 0, sizeof(nodes));
    }
    inline void pushup(int root) {
        nodes[root].value = nodes[Lchild(root)].value + nodes[Rchild(root)].value;
    }
    inline void build(int root, int l, int r) {
        nodes[root].tag_Set = 0;
        if (l == r)nodes[root].value = 0;
        else {
            int m = (l + r) >> 1;
            build(Lchild(root), l, m);
            build(Rchild(root), m + 1, r);
            pushup(root);
        }
    }
    inline void pushdown(int root, int l, int r) {
        int m = (l + r) >> 1;
        if(nodes[root].tag_Set) {
            nodes[Lchild(root)].tag_Set = nodes[Rchild(root)].tag_Set = nodes[root].tag_Set;
            nodes[Lchild(root)].value = (m - l + 1) * nodes[root].tag_Set;
            nodes[Rchild(root)].value = (r - m) * nodes[root].tag_Set;
            nodes[root].tag_Set = 0;
        }
    }
    inline void updateSet(int root, int curl, int curr, int tarl, int tarr, int k) {
        if (tarr < curl || curr < tarl)return;
        if (tarl <= curl && curr <= tarr) {
            nodes[root].tag_Set = k;
            nodes[root].value = (curr - curl + 1) * k;
            return;
        }
        pushdown(root, curl, curr);
        int m = (curl + curr) >> 1;
        if (tarl <= m) updateSet(Lchild(root), curl, m, tarl, tarr, k);
        if (tarr > m) updateSet(Rchild(root), m + 1, curr, tarl, tarr, k);
        pushup(root);
    }
    inline int query(int root, int curl, int curr, int tarl, int tarr) {
        if (tarr < curl || curr < tarl)return 0;
        if (tarl <= curl && curr <= tarr) {
            return nodes[root].value;
        }
        pushdown(root, curl, curr);
        int m = (curl + curr) >> 1;
        int ret = 0;
        if (tarl <= m) ret += query(Lchild(root), curl, m, tarl, tarr);
        if (tarr > m) ret += query(Rchild(root), m + 1, curr, tarl, tarr);
        return ret;
    }
    
};
SegmentTree tree;

int main() {
    n = read(), m = read();
    for(int i = 1; i <= m; ++i) {
        x[++x_size] = a[i].l = read();
        x[++x_size] = a[i].r = read();
    }
    sort(x + 1, x + x_size + 1);
    realx_size = unique(x + 1, x + x_size + 1) - x - 1;
    x_size = realx_size;
    for(int i = 2; i <= x_size; ++i)
        if(x[i] - x[i - 1] > 1) x[++realx_size] = x[i] - 1, x[++realx_size] = x[i - 1] + 1;
    x_size = realx_size;
    sort(x + 1, x + x_size + 1);
    realx_size = unique(x + 1, x + x_size + 1) - x - 1;
    tree.build(1, 1, realx_size);
    for(int i = 1; i <= m; ++i) {
        L = lower_bound(x + 1, x + realx_size + 1, a[i].l) - x;
        R = lower_bound(x + 1, x + realx_size + 1, a[i].r) - x;
        tree.updateSet(1, 1, realx_size, L, R, i);
    }
    for(int i = 1; i <= realx_size; ++i)
        c[i] = tree.query(1, 1, realx_size, i, i);
    for(int i = 1; i < realx_size; ++i)
        ans = (ans + sum(x[i], x[i + 1] - 1) * (1ll * c[i])) % MOD;
    ans = (ans + x[realx_size] * (1ll * c[realx_size])) % MOD;
    write(ans);
}


编辑于 2020-09-02 19:18:12 回复(3)
Java
景午头像 景午
100分。非暴力。用差分的思想。
创建数组存操作记录，在区间左端记录＋i，区间右端记录－i。
创建一个优先队列，从左往右遍历所有操作，遇到＋就add(i)，遇到－就remove(i)。
每个位置的密码就是这时优先队列大顶端的数。

（用PriorityQueue会超时，这里用布尔数组实现了同样的功能） 
import java.util.Scanner;

public class Main {

    static class Node {
        int i;
        boolean set;
        Node prev;

        public Node(int i, boolean set, Node prev) {
            this.i = i;
            this.set = set;
            this.prev = prev;
        }
    }

    static class PriorityQueue {
        private final boolean[] active;
        private int max;

        public PriorityQueue(int upperBound) {
            active = new boolean[upperBound + 1];
            active[0] = true;
            max = 0;
        }

        public void add(int i) {
            active[i] = true;
            if (i > max)
                max = i;
        }

        public void remove(int i) {
            active[i] = false;
            if (max == i)
                while (!active[max]) max--;
        }

        public int peek() {
            return max;
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        Node[] nodes = new Node[n + 1];
        for (int i = 1; i <= m; i++) {
            int l = sc.nextInt();
            int r = sc.nextInt();
            nodes[l] = new Node(i, true, nodes[l]);
            nodes[r + 1] = new Node(i, false, nodes[r + 1]);
        }
        long res = 0;
        PriorityQueue pq = new PriorityQueue(m);
        for (int index = 0; index < n; index++) {
            Node node = nodes[index];
            while (node != null) {
                if (node.set) {
                    pq.add(node.i);
                } else {
                    pq.remove(node.i);
                }
                node = node.prev;
            }
            int a_i = pq.peek();
            res = (res + (long) index * a_i) % 100000009L;
        }
        System.out.println(res);
    }
}
编辑于 2021-09-09 20:55:21 回复(2)
狼野1头像 狼野1 
#include<iostream>
#include <vector>
#include <queue>
#include <algorithm>
 
using namespace std;
 
struct node
{
    int l,r,v;
};
 
bool operator <(node a, node b){
 
    return a.v < b.v;
}
 
int cmp(node a, node b)
{
    return a.l < b.l;
}
int main()
{
    int n,m;
    while(cin>>n>>m)
    {
        vector<int> v = vector<int>(n);
        vector<node > tmp;
        for(int i = 1; i <= m;i++)
        {
            int a,b;
            cin>>a>>b;
            node now;
            now.l = a;
            now.r = b;
            now.v = i;
            tmp.push_back(now);
        }
        sort(tmp.begin(), tmp.end(), cmp);
        priority_queue<node> q;
        int pos = 0;
        for(int i = 0; i < n; i++)
        {
            int big = 0;
            while(i >= tmp[pos].l && pos < m)
            {
                node now = tmp[pos];
                q.push(tmp[pos]);
                pos++;
            }
            while(!q.empty())
            {
                node now = q.top();
                if(now.r < i)
                {
                    q.pop();
                }
                else
                {
                    v[i] = now.v;
                    break;
                }
            }
        }
        long long ans = 0;
        for(int i = 0 ;i < n; i++)
        {
            ans += i * v[i];
            ans %=  100000009;
        }
        cout<< ans<<endl;
    }
    return 0;
}
本题的思路，首先把所有的线段排序，按左边排序，然后每一次对数组进行修改的时候，都把包含这个点的线段添加到优先队列，然后判断优先队列的top线段是否包含这个点，包含直接修改值，不包含直接弹出队列，如果队列没有满足的，那么不修改默认为0，有满足的直接修改。
发表于 2021-07-20 01:12:49 回复(0)
云之端201902272219279头像 云之端201902272219279 
只过了30%，说是超时，不知道应该如何优化啊……

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        /**
         * int[n] int l int r int m
         * 1.读入n和m
         * 2.创建密码数组，初始值为0，长度为n
         * 3.建立循环，循环次数为m，进行m轮计算操作
         * 4.计算完成后，生成最终密码
         *
         * */
        //读入n和m
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        //创建密码数组，初始值为0，长度为n
        int[] password = new int[n];
        //建立循环，循环次数为m，进行m轮计算操作
        for (int i = 1; i <= m; i++) {
            int l = sc.nextInt();
            int r = sc.nextInt();
            for(int j = l;j<= r;j++){
                password[j]=i;
            }
        }
        long result = 0;
        for (int i = 0; i < password.length; i++) {
            result += (long)(i * password[i]);
        }
        result = result % 100000009L;
        //计算完成后，生成最终密码
        System.out.println(result);
    }
}

发表于 2020-09-08 20:31:26 回复(2)
C/C++
牛客451928974号头像 牛客451928974号 
#include<iostream>
using namespace std;
#define N 200000
int main()
{
    int cnum, M;
    cin >> cnum;
    cin >> M;
    int codemom[N] = { 0 };
    if (M == 0)
    {
        cout << "0" << endl;
    }
    else
    {
        int* arr = new int[2];
        for (int i = 0; i < M; i++)
        {
            int L, R;
            cin >> L;
            arr[0] = L;
            cin >> R;
            arr[1] = R;
            for (int j = L; j <= R; j++)
            {
                codemom[j] = i + 1;
     
            }

        }
        long long code = 0 ;
        
        for (int i = 0; i < cnum; i++)
        {
            code = code + i * codemom[i];

        }
        cout << code%100000009 << endl;
    }
}
一开始用的int code，一个没通过，改成long long以后通过三个；但是超时；
N=200000了就过不去了，我觉得还是code那里存不下这么大的数了，这咋办啊？
我是小菜 大佬们的代码我都看不懂555 看来我要去学数据结构和算法了
发表于 2022-04-24 22:00:05 回复(0)
不想九九六头像 不想九九六 
#include <iostream>
#include <vector>
using namespace std;
int main()
{
    int N = 0; // 槽位个数
    int M = 0; // 计算轮数
    cin >> N >> M;
    
    vector<int> Cao(N,0);
    // M 轮计算
    for(int i = 1; i <= M; i++){
        int L, R;
        cin >> L >> R; // 下标
        // 下标赋值
        for(int j = L; j <= R; j++){
            Cao[j] = i;
        }
    }
    // 生成密码
    unsigned int res = 0;
    for(unsigned int i = 0; i < N; i++){
       res += i * Cao[i];
    }
    res = res % 100000009;
    return 0;
}
给的例子测试没毛病，但是一个case都不通过，不知道啥毛病
发表于 2020-08-03 22:06:32 回复(4)
I/.O头像 I/.O
测试集都不给，开头就是一个 10000 10000  
public class Main {
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		int n = scanner.nextInt();
		int ctime=scanner.nextInt();
		int [] slot =new int[n];
		ArrayList<LinkedList<int[]>> areas =new ArrayList<>();
		int sum=0;
		for(int i =0;i<ctime;i++) {
			int [] area =new int[2];
			area[0] =scanner.nextInt();
			area[1] =scanner.nextInt();		
			LinkedList<int[]> ls =new LinkedList<int[]>();
			ls.add(area);
			areas.add(ls);
			for(int k=0;k<i;k++) {
				LinkedList<int[]> tmp =areas.get(k);
				LinkedList<int[]> newTmpLinkedList=new LinkedList<>();
				while(!tmp.isEmpty()) {
					int [] arr=tmp.removeFirst();
//					System.out.println(i+":"+Arrays.toString(arr));
					if(arr[0]>=area[0]&&arr[0]<=area[1]) { //起点再中间
						if(area[1]+1<=arr[1]) { //终点大
							newTmpLinkedList.add( new int[] {area[1]+1,arr[1]});
						}
					}else if (arr[1]>=area[0]&&arr[1]<=area[1]) {
							if(area[0]-1>=arr[0]) {
								newTmpLinkedList.add( new int[] {arr[0],area[0]-1});
							}						
				}
				else {
					newTmpLinkedList.add(arr);
				}	
					areas.set(k, newTmpLinkedList);
				}				
			}
		}
		for(int i =0 ;i<ctime;i++) {
			LinkedList<int[]> tmp =areas.get(i);
			for(int[] item :tmp) {
					for(int start =item[0];start<=item[1];start++) {
		
						sum=(sum+start*(i+1))%100000009;
					}
				
				
			}
			
		}
		
		System.out.println(sum);
	}

}


发表于 2020-07-22 20:46:35 回复(2)
左职新手头像 左职新手
用野狼的思路，Java代码需要使用BufferedReader读取输入，否则会超时 
import java.util.Scanner;
import java.util.*;
import java.io.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    // 枚举 + 优先队列
    // 枚举每个点，优先队列保存值最大的区间
    // 将区间按左端点排序，将左端点 <= 当前枚举点的 区间加入优先队列
    // 队列头的右端点 如果 >= 当前枚举点，对应的值即为该点的最终值
    // 如果 <，说明该区间不包括当前点，更不会包括之后的点，可以去除该区间
    static long mod = 100000009L;
    public static void main(String[] args) throws IOException {
        String[] input;
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));
        // 注意 hasNext 和 hasNextLine 的区别
        input = in.readLine().split(" ");
        int n = Integer.parseInt(input[0]);
        long m = Long.parseLong(input[1]);
        long i;
        ArrayList<Range> list = new ArrayList<>();
        PriorityQueue<Range> queue = new PriorityQueue<>(new Comparator<Range>() {
            @Override
            public int compare(Range r1, Range r2) {
                return (int)(r2.val - r1.val);
            }
        });
        long ans = 0L;
        for (i = 1; i <= m; i++) {
            input = in.readLine().split(" ");
            list.add(new Range(Long.parseLong(input[0]), Long.parseLong(input[1]), i));
        }
        list.sort(new Comparator<Range>() {
            @Override
            public int compare(Range r1, Range r2) {
                return (int)(r1.l - r2.l);
            }
        });
        int j = 0;
        for (i = 0; i < n; i++) {
            while (j < list.size() && list.get(j).l <= i) {
                queue.add(list.get(j));
                j++;
            }
            while (!queue.isEmpty()) {
                if (queue.peek().r >= i) {
                    ans = (ans + ((i * queue.peek().val) % mod)) % mod;
                    break;
                } else {
                    queue.poll();
                }   
            }
        }
        out.write(String.valueOf(ans));
        out.newLine();
        out.flush();
    }

    static class Range {
        long l;
        long r;
        long val;
        public Range(long l, long r, long val) {
            this.l = l;
            this.r = r;
            this.val = val;
        }
    }
}


发表于 2022-12-17 11:41:23 回复(0)
helloMr.right头像 helloMr.right 
#include <vector>
#include <cstdio>
using namespace std;
const int N = 1.5 * 1e7 + 10, MOD = 1e8 + 9;
int w[N], p[N];

typedef pair<int, int> PII;

vector<PII> v;
//并查集

int find(int x)
{
    if(x != p[x]) p[x] = find(p[x]);
    return p[x];
}

void join(int x, int y)
{
    int px = find(x), py = find(y);
    if(px != py)
    {
        p[px] = py;
    }
}

int main()
{
    int n, m;
    scanf("%d%d", &n, &m);
    for(int i = 0; i < N; i++) p[i] = i;
    
    for(int i = 0; i < m; i++)
    {
        int a, b;
        scanf("%d%d", &a, &b);
        v.push_back({a, b});
    }
    
    //倒着染色
    for(int i = m; i; i--)
    {
        int l = v[i-1].first, r = v[i-1].second;
        
        int r1 = find(l);
        while(r1 <= r)
        {
            w[r1] = i;
            join(r1, r1 + 1);
            r1 = find(r1);
        }
        
    }
    
    long long sum = 0;
    
    for(int i = 0; i < n; i++)
    {
        sum += (1ll * i * w[i])%MOD;
    }
    
    printf("%lld\n", sum % MOD);
    
    return 0;
}

发表于 2022-04-14 19:38:07 回复(2)
炖蘑菇汤头像 炖蘑菇汤
在插入区间的时候计算第m次的密码和 
import java.util.*;

public class Main {


    static long res = 0L;
    static long mod = 100000009L;
    public static void main(String[] args) {

        Scanner in = new Scanner(System.in);
        in.nextInt();
        int m = in.nextInt();
        ArrayList<Integer> list = new ArrayList<>();
        int[][] edge = new int[m + 1][2];
        for (int i = 1; i <= m; i++) {
            edge[i][0] = in.nextInt();
            edge[i][1] = in.nextInt();
        }
        ArrayList<int[]> interval = new ArrayList<>();
        for (int i = edge.length - 1; i > 0; i--) {
            interval = insertInterval(interval, edge[i], i);
        }
        System.out.println(res);
    }

    public static ArrayList<int[]> insertInterval(ArrayList<int[]> interval, int[] newInterval, int m) {
        int[] temp = null;
        ArrayList<int[]> list = new ArrayList<>();
        int i = 0;
        for ( ; i < interval.size(); i++) {
            int left = interval.get(i)[0];
            int right = interval.get(i)[1];
            if (newInterval[0] <= right) {
                temp = new int[2];
                if (newInterval[0] < left) {
                    temp[0] = newInterval[0];
                    if (newInterval[1] < left) {
                        compute(newInterval[0], newInterval[1], m);
                    } else {
                        compute(newInterval[0], left - 1, m);
                    }
                } else {
                    temp[0] = left;
                }
                
                if (newInterval[1] < left) {
                    temp[1] = newInterval[1];
                    list.add(temp);
                    break;
                } else if (newInterval[1] > right) {
                    int j = i + 1;
                    for ( ; j < interval.size(); j++) {
                        left = interval.get(j)[0];
                        right = interval.get(j)[1];
                        if (newInterval[1] < left) {
                            temp[1] = newInterval[1];
                            list.add(temp);
                            i = j;
                            compute(interval.get(j - 1)[1] + 1, newInterval[1], m);
                            break;
                        } else if (newInterval[1] > right) {
                            compute(interval.get(j - 1)[1] + 1, left - 1, m);
                        } else {
                            temp[1] = right;
                            list.add(temp);
                            i = j + 1;
                            compute(interval.get(j - 1)[1] + 1, left - 1, m);
                            break;
                        }
                    }
                    if (j == interval.size()) {
                        temp[1] = newInterval[1];
                        list.add(temp);
                        i = j;
                        compute(interval.get(j - 1)[1] + 1, newInterval[1], m);
                    }
                    break;
                } else {
                    temp[1] = right;
                    list.add(temp);
                    i = i + 1;
                    break;
                }
            } else {
                list.add(interval.get(i));
            }
        }

        for (int j = i; j < interval.size(); j++) {
            list.add(interval.get(j));
        }
        
        if (temp == null) {
            list.add(newInterval);
            compute(newInterval[0], newInterval[1], m);
        }
        return list;
    }

    public static void compute(int left, int right, int m) {
        for (int i = left; i <= right; i++) {
            res = (res + 1L * m * i ) % mod;
        }
    }
}


发表于 2022-04-14 10:31:52 回复(0)
牛客510061697号头像 牛客510061697号
有人告诉我，这哪里错了吗？我这显示一个例子都不对，人快傻了
#include<iostream>
#include<string>
using namespace std;
int main()
{
    int s, b;
    cin >> s >> b;
    int sk[10000];
    int sz[10000][2];
    for (int a = 0; a < b; a++)
    {
        cin >> sz[a][1] >> sz[a][2];
    }
    for (int a = 0; a < s; a++)
    {
        sk[a] = 0;
    }
    for (int a = 0; a < b; a++)
    {
        if (sz[a][1] > sz[a][2])
        {
            long int temp = sz[a][1];
            sz[a][1] = sz[a][2];
            sz[a][2] = temp;
        }
    }
    for (int a = 0; a <b; a++)
    {
        for (int g = sz[a][1]; g <= sz[a][2]; g++)
        {
            sk[g] =a +1;
        }
    }
    int sum = 0;
    for (int a = 0; a < s; a++)
    {
        sum = sum + sk[a] * a;
    }
    cout << sum << endl;
}
发表于 2022-03-11 16:33:10 回复(0)
连三月s头像 连三月s
同过8个然后超时，照着上面2个兄弟的写的。 
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int[][] ops = new int[m][3];
        for (int i = 0; i < m; i++) {
            int left = sc.nextInt();
            int right = sc.nextInt();
            ops[i][0] = left;
            ops[i][1] = right;
            ops[i][2] = i + 1;
        }
        // 根据左端点排序
        Arrays.sort(ops, (o1, o2) -> o1[0] - o2[0]);
  //      for (int i = 0; i < m; i++) {
    //        System.out.println(ops[i][0] +":" +ops[i][1] +":" + ops[i][2]);
     //   }
        // 结果
        int[] v = new int[n];
        // 放入一些操作, 后面进的操作要放在最上面。
        PriorityQueue<int[]> pq = new PriorityQueue<>((o1,o2) -> o2[2] - o1[2]);
        int idx = 0;
        for (int i = 0; i < n; i++) {
            // 将操作左端点包含i位置的都入优先队列 
            while (idx < m && ops[idx][0] <= i) pq.offer(ops[idx++]);
            // 此时队顶元素如果满足要求，那么i的位置就是他。
            // 但是可能会出现很多不满足的
            // 举个例子： 比如 i = 8
            // 然后堆中还有 [3,6,1], [1, 2,5], [3,5,7]等，这些无用的，需要出队
            while (!pq.isEmpty()) {
//                System.out.println("left:"+pq.peek()[0]+" right:"+pq.peek()[1]);
                if (pq.peek()[1] < i) pq.poll();
                else {
                    v[i] = pq.peek()[2];
                    break;
                }
            }
        }
       // for (int i = 0; i < n; i++) {
        //    System.out.print(v[i]+" ");
        //}
        long res = 0;
        for (int i = 0; i < n; i++) {
            res = res +  1L * i * v[i];
            res = res % 100000009;
        }
        System.out.println(res);
    }
}

发表于 2022-03-08 12:17:21 回复(0)
差的远头像 差的远
我就知道事情不是那么简单的， 果真， 给我搞了一个线段树
发表于 2021-10-06 21:56:06 回复(0)
为了睡觉头像 为了睡觉

用上面的用户狼野1的C++代码改的Java代码，他那个C++代码能直接通过所有用例还不超时，我这个只能通过8个用例就超时了。

图片说明
提交运行了好多次，有时能通过9个用例再超时，有时能通过全部用例。 

import java.util.*;

public class Main {
    public static void main(String[] args) {

        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int m = in.nextInt();

        Node[] tmp = new Node[m];
        long[] arr = new long[n];
        for (int i = 1; i <= m; i++) {
            int l = in.nextInt();
            int r = in.nextInt();
            Node node = new Node(l,r,i);
            tmp[i-1]=node;
        }

        Arrays.sort(tmp, new Comparator<Node>() {
            public int compare(Node a, Node b) {
                return a.l- b.l;
            }
        });

        Comparator<Node> vComparator = new Comparator<Node>(){
            @Override
            public int compare(Node a, Node b) {
                return b.v - a.v;
            }
        };

        Queue<Node> nodePriorityQueue = new PriorityQueue<Node>(7, vComparator);

        int pos = 0;
        for(int i = 0; i < n; i++)
        {
            while(pos < m && i >= tmp[pos].l )
            {
                nodePriorityQueue.add(tmp[pos]);
                pos++;
            }
            while(!nodePriorityQueue.isEmpty())
            {
                Node now = nodePriorityQueue.peek();
                if(now.r < i)
                {
                    nodePriorityQueue.poll();
                }
                else
                {
                    arr[i] = now.v;
                    break;
                }
            }
        }

/*        BigInteger result = new BigInteger("0");
        for (int i = 0; i < arr.length; i++) {
            result = result.add(new BigInteger(String.valueOf(i * arr[i])));
            result = result.divideAndRemainder(new BigInteger(String.valueOf(100000009)))[1];
        }*/

        long result = 0;
        for (int i = 0; i < arr.length; i++) {
            result = result + i * arr[i];
            result = result % 100000009;
        }

        System.out.println(result);
    }
}

class Node {
    int l, r, v;

    public Node(int l, int r, int v) {
        this.l = l;
        this.r = r;
        this.v = v;
    }
}
编辑于 2021-09-04 01:14:37 回复(0)
Python
勇敢牛牛不怕面试头像 勇敢牛牛不怕面试 
NM = input().split()
n,times = int(NM[0]),int(NM[1])
org = [0]*n
for i in range(times):
    LR = input().split()
    L,R = int(LR[0]),int(LR[1])
    org[L:R+1] = [i+1]*(R+1-L)
ans = 0
for j in range(n):
    ans+= j*org[j]
print(ans % 100000009)

只能过30%
```

编辑于 2021-08-17 11:24:14 回复(0)
thundersoft_tzp头像 thundersoft_tzp
这道题直接利用递归来做感觉会方便点了，附上部分代码：
int* mima(int a[],int m,int s,int n)
{
  if(s>m)
  {
    return a;
  }
  int L,R;
  cin >>L>>R;
  while(L > n-1 || R > n-1)
  {
    cout <<"pls reinput L&R number!!!!"<<endl;
    cin >> L>>R;
  }
  for(int i =L;i<=R;i++)
  {
    a[i]=s;
  }
  s++;
  mima(a,m,s,n);
}
其中m为最大轮数，s为当前轮数，s从1开始，这样得到的数组a的排列，就是最后的密码。然后在对数组a进行（0*a[0] + 1*a[1] + 2*a[2] + ... + (N-1)*a[N-1]) 的简单求和就行了
发表于 2020-11-13 10:27:22 回复(0)
fycoder头像 fycoder

使用双栈记录区间，通过70%,还是超时了。。。

#include <iostream>
#include <vector>
#include <stack>

using namespace std;

int n, m, i, j;
int main() {
    cin >> n >> m;
    vector<int> v(n, 0);
    stack<vector<int>> s1, s2;
    for (int k = 1; k <= m; k++) {
        cin >> i >> j;
        if (s1.empty()) {
            s1.push({i, k, 0});
            s1.push({j, k, 1});
        } else {
            if (s1.top()[0] < i) {
                s1.push({i, k, 0}); //0代表左区间，1代表右区间
                s1.push({j, k, 1});
            } else {
                while (!s1.empty() && s1.top()[0] >= i) {
                    s2.push(s1.top());s1.pop();
                }
                if (!s1.empty() && i - s1.top()[0] != 1 && !s2.empty()) {
                    s1.push({i-1, s2.top()[1], s2.top()[2]});
                }
                s1.push({i,k,0});
                while (!s2.empty() && s2.top()[0] <= j) {
                    s2.pop();
                }
                s1.push({j,k,1});
                while (!s2.empty()) {
                    s1.push(s2.top());
                    s2.pop();
                }
            }
        }
    }
    char um[2] = {'l', 'r'};
    int end, beg;
    while (s1.size() > 1) {
        end = s1.top()[0];
        int val1 = s1.top()[1];
        char c1 = um[s1.top()[2]];
        s1.pop();
        beg = s1.top()[0];
        int val2 = s1.top()[1];
        char c2 = um[s1.top()[2]];
        if (c1 == 'r' && c2 == 'r') {
            for (int i = end; i > beg; i--) {
                v[i] = val1;
            }
        } else if (c2 == 'l' && c1 == 'l'){
            for (int i = beg; i < end; i++) {
                v[i] = val2;
            }
        } else if (c2 == 'l' && c1 == 'r') {
            for (int i = beg; i <= end; i++) {
                v[i] = val2;
            }
        }
    }
    long long res = 0;
    for (int i = 1; i < n; i++) {
        res += i * v[i];
        res %= 100000009;
    }
    cout << res << endl;
}
发表于 2020-09-08 10:49:30 回复(0)
提交观点

问题信息

C++工程师 golang工程师 搜狗 小米集团 测试工程师 PHP工程师 2020 2021 Java工程师
来自：【2021】小米秋招软...
上传者：小小
难度：
31条回答 151378浏览

热门推荐

通过挑战的用户

相关试题

密码生成

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号