1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
#include <bits/stdc++.h>
using namespace std;
using ll = unsigned long long;
const int maxN = 1 << 19;
int t[maxN];
int I[maxN];

const int mod = 1100000017;
const int p = 1e9 + 9;

struct Hash {
    ll h0, h1;
    Hash(int x = 0)
    : h0(x), h1(x) {}

    Hash(ll h0, ll h1)
    : h0(h0), h1(h1) {}

    Hash operator*(Hash const& o) const {
        return { h0 * o.h0, h1 * o.h1 % mod };
    }

    Hash operator+(Hash const& o) const {
        return { h0 + o.h0, h1 + o.h1 % mod };
    }
    
    bool operator==(Hash const& o) const {
        return h0 == o.h0 && h1 == o.h1;
    }
};

struct Node {
    Node *t0;
    Node *t1;
    Hash hsh;

    Node(int val)
    : t0(nullptr), t1(nullptr), hsh(val) {}

    Node(Node *t0, Node* t1, Hash pow)
    : t0(t0), t1(t1), hsh(t0->hsh * pow + t1->hsh) {}
};

int r, n, LVL, m;
Node *tree[maxN];
Hash ppow[32];


Node *build(int x, int lvl) {
    if(x < r) {
        Node *a = build(2 * x, lvl - 1);
        Node *b = build(2 * x + 1, lvl - 1);
        return new Node(a, b, ppow[lvl]);
    }
    assert(lvl == 0);
    return new Node(t[x - r]);
}

Node *add(int qa, int wat, int ta, int tb, Node* x, int lvl) {
    if(qa == ta && tb == ta)
        return new Node(wat);
    int avg = (ta + tb) / 2;
    if(qa <= avg) return new Node(add(qa, wat, ta, avg, x->t0, lvl-1), x->t1, ppow[lvl]);
    else return new Node(x->t0, add(qa, wat, avg+1, tb, x->t1, lvl-1), ppow[lvl]);
}


bool treecmp(Node *a, Node *b, int lvl) {
    if(lvl == 0) return a->hsh.h0 < b->hsh.h0;
    if(a->t0->hsh == b->t0->hsh) return treecmp(a->t1, b->t1, lvl-1);
    return treecmp(a->t0, b->t0, lvl-1);
}

bool cmp(int a, int b) {
    if(tree[a]->hsh == tree[b]->hsh) return a < b;
    return treecmp(tree[a], tree[b], LVL);
}

int main() {
    ppow[0] = 1;
    ppow[1] = p;
    for(int i = 2; i < 22; ++i) ppow[i] = ppow[i - 1] * ppow[i - 1];

    scanf("%d%d", &n, &m);
    for(int i = 0; i < n; ++i) scanf("%d", t + i);

    r = 1;
    while(r < n) {
        r *= 2;
        LVL++;
    }
    tree[0] = build(1, LVL);
    
    for(int x, a, i = 1; i < m; ++i) {
        scanf("%d%d", &x, &a);
        tree[i] = add(x - 1, a, 0, r - 1, tree[i - 1], LVL);
        I[i] = i;
    }
    
    sort(I, I + m, cmp);
    for(int i = 0; i < m; ++i) printf("%d ", I[i] + 1);
    puts("");
}