package main
import (  "fmt"  "math/rand"  "time")
// 桶，得分在有序表里！桶只作为有序表里的value，不作为keytype Bucket struct {  head *Node  tail *Node}
func NewBucket() *Bucket {  head := &Node{index: -1}  tail := &Node{index: -1}  head.next = tail  tail.last = head  return &Bucket{head: head, tail: tail}}
func (b *Bucket) add(node *Node) {  node.last = b.tail.last  node.next = b.tail  b.tail.last.next = node  b.tail.last = node}
func (b *Bucket) merge(join *Bucket) {  if join.head.next != join.tail {    b.tail.last.next = join.head.next    join.head.next.last = b.tail.last    join.tail.last.next = b.tail    b.tail.last = join.tail.last    join.head.next = join.tail    join.tail.last = join.head  }}
// Node represents a node in the buckettype Node struct {  index int  last  *Node  next  *Node}
func (n *Node) connectLastNext() {  n.last.next = n.next  n.next.last = n.last}
// 暴力方法func operateScores1(scores []int, operations [][]int) []int {  n := len(scores)  ans := make([]int, n)  copy(ans, scores)
  for _, op := range operations {    if op[0] == 1 {      for i := 0; i < n; i++ {        ans[i] = max(ans[i], op[1])      }    } else {      ans[op[1]] = op[2]    }  }
  return ans}
// 正式方法func operateScores2(scores []int, operations [][]int) []int {  n := len(scores)  nodes := make([]*Node, n)  scoreBucketMap := make(map[int]*Bucket)
  for i := 0; i < n; i++ {    nodes[i] = &Node{index: i}    if _, ok := scoreBucketMap[scores[i]]; !ok {      scoreBucketMap[scores[i]] = NewBucket()    }    scoreBucketMap[scores[i]].add(nodes[i])  }
  for _, op := range operations {    if op[0] == 1 {      floorKeyV := floorKey(scoreBucketMap, op[1]-1)
      if floorKeyV != -1 && scoreBucketMap[op[1]] == nil {        scoreBucketMap[op[1]] = NewBucket()      }
      for floorKeyV != -1 {        scoreBucketMap[op[1]].merge(scoreBucketMap[floorKeyV])        delete(scoreBucketMap, floorKeyV)        floorKeyV = floorKey(scoreBucketMap, op[1]-1)      }    } else {      cur := nodes[op[1]]      cur.connectLastNext()
      if scoreBucketMap[op[2]] == nil {        scoreBucketMap[op[2]] = NewBucket()      }
      scoreBucketMap[op[2]].add(cur)    }  }
  ans := make([]int, n)  for score, bucket := range scoreBucketMap {    cur := bucket.head.next    for cur != bucket.tail {      ans[cur.index] = score      cur = cur.next    }  }
  return ans}
func floorKey(m map[int]*Bucket, target int) int {  for score := range m {    if score <= target {      return score    }  }  return -1}
func max(a, b int) int {  if a > b {    return a  }  return b}
// RandomScores generates an array of random scoresfunc randomScores(n, v int) []int {  scores := make([]int, n)  rand.Seed(time.Now().UnixNano())  for i := 0; i < n; i++ {    scores[i] = rand.Intn(v)  }  return scores}
// RandomOperations generates a 2D array of random operationsfunc randomOperations(n, m, v int) [][]int {  operations := make([][]int, m)  rand.Seed(time.Now().UnixNano())  for i := 0; i < m; i++ {    operations[i] = make([]int, 3)    if rand.Float32() < 0.5 {      operations[i][0] = 1      operations[i][1] = rand.Intn(v)    } else {      operations[i][0] = 2      operations[i][1] = rand.Intn(n)      operations[i][2] = rand.Intn(v)    }  }  return operations}
// IsEqual checks if two arrays are equalfunc isEqual(arr1, arr2 []int) bool {  if len(arr1) != len(arr2) {    return false  }  for i := 0; i < len(arr1); i++ {    if arr1[i] != arr2[i] {      return false    }  }  return true}
// Main function for testingfunc main() {  N := 1000  M := 1000  V := 100000  testTimes := 100  fmt.Println("功能测试开始")  for i := 0; i < testTimes; i++ {    n := rand.Intn(N) + 1    m := rand.Intn(M) + 1    scores := randomScores(n, V)    operations := randomOperations(n, m, V)    ans1 := operateScores1(scores, operations)    ans2 := operateScores2(scores, operations)    if !isEqual(ans1, ans2) {      fmt.Println("出错了！")    }  }  fmt.Println("功能测试结束")
  fmt.Println("性能测试开始")  n := 100000  m := 100000  v := 100000000  scores := randomScores(n, v)  operations := randomOperations(n, m, v)  fmt.Println("总人数:", n)  fmt.Println("操作数:", n)  fmt.Println("值范围:", v)  start := time.Now()  operateScores2(scores, operations)  end := time.Now()  fmt.Println("运行时间:", end.Sub(start))  fmt.Println("性能测试结束")}

#include <iostream>#include <vector>#include <map>#include <random>#include <ctime>
using namespace std;
class Bucket;
// Node represents a node in the bucketclass Node {public:    int index;    Node* last;    Node* next;
    void connectLastNext() {        last->next = next;        next->last = last;    }};
// Bucket, scores stored in a sorted listclass Bucket {public:    Node* head;    Node* tail;
    Bucket() {        head = new Node();        tail = new Node();        head->index = -1;        tail->index = -1;        head->next = tail;        tail->last = head;    }
    void add(Node* node) {        node->last = tail->last;        node->next = tail;        tail->last->next = node;        tail->last = node;    }
    void merge(Bucket* join) {        if (join->head->next != join->tail) {            tail->last->next = join->head->next;            join->head->next->last = tail->last;            join->tail->last->next = tail;            tail->last = join->tail->last;            join->head->next = join->tail;            join->tail->last = join->head;        }    }};
vector<int> operateScores1(const vector<int>& scores, const vector<vector<int>>& operations) {    int n = scores.size();    vector<int> ans(scores);
    for (const auto& op : operations) {        if (op[0] == 1) {            for (int i = 0; i < n; i++) {                ans[i] = max(ans[i], op[1]);            }        }        else {            ans[op[1]] = op[2];        }    }
    return ans;}
int floorKey(const map<int, Bucket*>& m, int target);
vector<int> operateScores2(const vector<int>& scores, const vector<vector<int>>& operations) {    int n = scores.size();    vector<Node*> nodes(n);    map<int, Bucket*> scoreBucketMap;
    for (int i = 0; i < n; i++) {        nodes[i] = new Node();        nodes[i]->index = i;        if (scoreBucketMap.find(scores[i]) == scoreBucketMap.end()) {            scoreBucketMap[scores[i]] = new Bucket();        }        scoreBucketMap[scores[i]]->add(nodes[i]);    }
    for (const auto& op : operations) {        if (op[0] == 1) {            int floorKeyV = floorKey(scoreBucketMap, op[1] - 1);
            if (floorKeyV != -1 && scoreBucketMap.find(op[1]) == scoreBucketMap.end()) {                scoreBucketMap[op[1]] = new Bucket();            }
            while (floorKeyV != -1) {                scoreBucketMap[op[1]]->merge(scoreBucketMap[floorKeyV]);                scoreBucketMap.erase(floorKeyV);                floorKeyV = floorKey(scoreBucketMap, op[1] - 1);            }        }        else {            Node* cur = nodes[op[1]];            cur->connectLastNext();
            if (scoreBucketMap.find(op[2]) == scoreBucketMap.end()) {                scoreBucketMap[op[2]] = new Bucket();            }
            scoreBucketMap[op[2]]->add(cur);        }    }
    vector<int> ans(n);    for (const auto& entry : scoreBucketMap) {        int score = entry.first;        Bucket* bucket = entry.second;        Node* cur = bucket->head->next;        while (cur != bucket->tail) {            ans[cur->index] = score;            cur = cur->next;        }    }
    return ans;}
int floorKey(const map<int, Bucket*>& m, int target) {    for (const auto& entry : m) {        int score = entry.first;        if (score <= target) {            return score;        }    }    return -1;}
int main() {    int N = 1000;    int M = 1000;    int V = 100000;    int testTimes = 100;    cout << "功能测试开始" << endl;    for (int i = 0; i < testTimes; i++) {        int n = rand() % N + 1;        int m = rand() % M + 1;        vector<int> scores(n);        vector<vector<int>> operations(m, vector<int>(3));
        for (int j = 0; j < n; j++) {            scores[j] = rand() % V;        }
        for (auto& op : operations) {            if (rand() < 0.5) {                op[0] = 1;                op[1] = rand() % V;            }            else {                op[0] = 2;                op[1] = rand() % n;                op[2] = rand() % V;            }        }
        vector<int> ans1 = operateScores1(scores, operations);        vector<int> ans2 = operateScores2(scores, operations);
        if (ans1 != ans2) {            cout << "出错了！" << endl;        }    }    cout << "功能测试结束" << endl;
    cout << "性能测试开始" << endl;    int n = 1000000;    int m = 1000000;    int v = 1000000000;    vector<int> scores(n);    vector<vector<int>> operations(m, vector<int>(3));
    for (int i = 0; i < n; i++) {        scores[i] = rand() % v;    }
    for (auto& op : operations) {        op[0] = rand() < 0.5 ? 1 : 2;        op[1] = rand() % n;        op[2] = rand() % v;    }
    cout << "总人数: " << n << endl;    cout << "操作数: " << m << endl;    cout << "值范围: " << v << endl;    clock_t start = clock();    operateScores2(scores, operations);    clock_t end = clock();    cout << "运行时间: " << double(end - start) / CLOCKS_PER_SEC << endl;    cout << "性能测试结束" << endl;
    return 0;}