Untitled

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

typedef struct Classmate {
    long long int power;
    long long int label;
    long long int rank;

    long long int *attackHistory;
    long long int *prefixSum;      // 动态数组：前缀和
    long long int historyCapacity; // 记录攻击历史的容量
    long long int attackCount;
    bool needsRewardUpdate;     // 是否需要更新奖励

    struct Classmate *next;
    struct Classmate *previous;
} Classmate;

Classmate *head = NULL;

Classmate* createClassmate() {
    Classmate *newClassmate = (Classmate*)malloc(sizeof(Classmate));
    newClassmate->label = 0;
    newClassmate->rank = 0;
    newClassmate->power = 0;
    newClassmate->attackHistory = (long long int*)malloc(sizeof(long long int)); // 初始大小为1
    newClassmate->prefixSum = (long long int*)malloc(sizeof(long long int));
    newClassmate->attackCount = 0;
    newClassmate->historyCapacity = 1; // 初始容量为1
    newClassmate->needsRewardUpdate = false;
    newClassmate->next = NULL;
    newClassmate->previous = NULL;
    return newClassmate;
}

void appendClassmate(Classmate *classmate) {
    if (head == NULL) {
        head = classmate;
    } else {
        Classmate *current = head;
        while (current->next != NULL) {
            current = current->next;
        }
        current->next = classmate;
        classmate->previous = current;
    }
}


void rewardPower() {
    Classmate *current = head;
    if(current == NULL) { return; }
    while (current != NULL) {
        current->needsRewardUpdate = true; // 标记为待更新
        current = current->next;
    }
}

void updateRewardsIfNeeded(Classmate *classmate , long long int N) {
    if (classmate->needsRewardUpdate) {
        // 这里添加计算力量值的逻辑，例如：
        classmate->power += (N- classmate->rank); // 假设 N 是全局变量或以其他方式获得
        classmate->needsRewardUpdate = false;
    }
}

void addAttackRecord(long long int attackerLabel , long long int N) {
    Classmate *attacker = head;

    if(attacker == NULL ){return ; }

    // 查找攻击者
    while (attacker != NULL && attacker->label != attackerLabel) { attacker = attacker->next; }
    
    if (attacker == NULL || attacker->rank == 1) {
        return; // 没有找到攻击者或者攻击者已经是第一名
    }

    Classmate *target = attacker->previous;
    if (target == NULL) {
        return; // 没有目标或者目标已经是最后一名
    }

    if (attacker->attackCount == attacker->historyCapacity) {
        // 当数组满时，扩大数组大小
        attacker->historyCapacity *= 2; // 容量加倍
        attacker->attackHistory = (long long int*)realloc(attacker->attackHistory, sizeof(long long int) * attacker->historyCapacity);
        attacker->prefixSum = (long long int*)realloc(attacker->prefixSum, sizeof(long long int) * attacker->historyCapacity);
    }

    // 在交换排名前更新攻击者和目标的奖励
    updateRewardsIfNeeded(attacker, N);
    updateRewardsIfNeeded(target , N);

    // 更新能量
    int powerIncrease = 0;
    if (attacker->power != target->power) {
        powerIncrease = target->power - attacker->power;
        attacker->power = target->power;
    }

    // 更新攻击历史和前缀和
    attacker->attackHistory[attacker->attackCount] = powerIncrease;
    attacker->prefixSum[attacker->attackCount] = (attacker->attackCount == 0) ? powerIncrease : attacker->prefixSum[attacker->attackCount - 1] + powerIncrease;
    attacker->attackCount++;

    // 交换排名
    int tempRank = attacker->rank;
    attacker->rank = target->rank;
    target->rank = tempRank;

    // 交换节点位置
    Classmate *prevTarget = target->previous;
    Classmate *attackerNext = attacker->next;

    if (prevTarget != NULL) {
        prevTarget->next = attacker;
    } else {
        head = attacker; // 更新头节点
    }
    attacker->previous = prevTarget;

    target->next = attackerNext;
    if (attackerNext != NULL) {
        attackerNext->previous = target;
    }
    attacker->next = target;
    target->previous = attacker;

    //     // 如果攻击者现在是第一名，则更新head指针
    // if (attacker->rank == 1) { head = attacker; }
}

void queryPower(long long int qi , long long int N) {
    Classmate *current = head;

    if(current == NULL) { return; }
    while (current != NULL) {
        updateRewardsIfNeeded(current , N);  // 确保力量值是最新的
        if (current->power >= qi) {
            printf("%lld %lld\n", current->rank, current->label);
            return; // 找到符合条件的同学并输出
        }
        current = current->next;
    }

    printf("0 0\n"); // 如果没有符合条件的同学
}

// void queryPower(long long int qi , long long int N) {
//     Classmate *current = head;

//     if(current == NULL ){return ; }
//     while (current != NULL) { 
//         updateRewardsIfNeeded(current , N);  // 确保力量值是最新的

//         if(current->power >= qi) { current = current->next; }
//     }

//     if (current != NULL && current->previous != NULL && current->previous->power >= qi) {
//         current = current->previous; // 向前移动一个节点以报告正确的同学
//         printf("%lld %lld\n", current->rank, current->label);
//     } else {
//         printf("0 0\n"); // 如果没有符合条件的同学
//     }
// }


void queryAttackHistory(long long int bi, long long int mi) {
    Classmate *current = head;

    if (current == NULL) { return; }
    while (current != NULL && current->label != bi) {
        current = current->next;
    }

    if (current == NULL) { return; }
    if (mi > current->attackCount) { mi = current->attackCount; }

    long long int startIdx = current->attackCount - mi;
    if (startIdx < 0) { startIdx = 0; }

    // 计算增加的总力量
    long long int totalIncrease = 0;
    if (mi > 0) {
        long long int lastIdx = current->attackCount - 1;
        totalIncrease = current->prefixSum[lastIdx];
        if (startIdx > 0) {
            totalIncrease -= current->prefixSum[startIdx - 1];
        }
    }

    printf("%lld\n", totalIncrease);
}

// 比较两个Classmate指针的label
int compareByLabel(const void *a, const void *b) {
    Classmate *classmateA = *(Classmate**)a;
    Classmate *classmateB = *(Classmate**)b;
    return classmateA->label - classmateB->label;
}

void printGameRecordByLabel(long long int N) {
    Classmate *current = head;
    Classmate *array[N]; // 存储Classmate指针的数组
    long long int index = 0;

    // 填充数组
    while (current != NULL) {
        array[index++] = current;
        current = current->next;
    }

    // 按label排序
    qsort(array, N, sizeof(Classmate*), compareByLabel);

    // 按排序后的顺序打印每个同学的攻击历史
    for (long long int i = 0; i < N; i++) {
        printf("%lld ", array[i]->attackCount);
        for (int j = 0; j < array[i]->attackCount; j++) {
            printf("%lld ", array[i]->attackHistory[j]);
        }
        printf("\n");
    }
}

void freeClassmates() {
    Classmate *current = head;
    while (current != NULL) {
        Classmate *temp = current;
        current = current->next;
        free(temp->attackHistory); // 释放攻击历史数组
        free(temp->prefixSum);
        free(temp); // 释放Classmate节点
    }
    head = NULL; // 将头指针设为空，避免悬挂指针
}


int main() {
    long long int Classmates_num, operation_nums, recent_attacks;
    
    // 读取同学数量 N 和操作数量 T
    scanf("%lld %lld %lld", &Classmates_num, &operation_nums,&recent_attacks);

    // 初始化同学信息
    for (int i = 0; i < Classmates_num; ++i) {
        int power;
        scanf("%lld", &power);
        Classmate *player = createClassmate();
        player->rank = i + 1;
        player->label = i+1;

        player->power = power;
        appendClassmate(player);
    }

    // 根据操作类型处理事件
    for (long long int i = 0; i < operation_nums; ++i) {   
        long long int operation_type;
        scanf("%lld", &operation_type);
        switch (operation_type) {
            case 1: {
                long long int attackerLabel;
                scanf("%lld", &attackerLabel);
                addAttackRecord(attackerLabel , Classmates_num);
                break;
            }
            case 2:
                rewardPower();
                break;
            case 3: {
                long long int qi;
                scanf("%lld", &qi);
                queryPower(qi , Classmates_num);
                break;
            }
            case 4: {
                long long int bi, mi;
                scanf("%lld %lld", &bi, &mi);
                queryAttackHistory(bi, mi);
                break;
            }
        }
    }
    printf("\n");
    printGameRecordByLabel(Classmates_num);

    // 清理资源
    freeClassmates();
    // ...
    return 0;
}