CodeForces - 878D 반복(검색)

1781 단어 递归
시작은 k개의 생물, n개의 속성이 3가지 조작을 지원합니다: 1.두 생물을 하나의 새로운 생물로 합치면 모든 속성 값은 원래의 비교적 큰 값이다.두 생물을 하나의 새로운 생물로 합치면 모든 속성 값은 원래의 작은 값이다.i생물의 j번째 속성 값 묻기
n<=1e5 k<=12 q<=1e5
Input
세 개의 수 nkq는 각각 속성수, 생물수와 조작수 이후 k줄마다 n개의 정수를 표시하고 생물 속성([1,1e9]에 속함)을 나타낸 후 q줄마다 3개의 수가 하나의 조작에 대응한다
Output
매번 질문 출력 한 줄에 대해 답을 표시합니다
Example
Input1 3 2 4 1000000000 1000000000 1 1 1000000000 1000000000 1 1 2 2 1 2 3 3 2 3 4 2Input2 1 3 2 3 2 1 2 1 3 3 4 1
Output1 1000000000 1000000000Output2 1
Note
첫 번째 사례에 대해 세 번째 생물 속성은 1000000000000100000000000이고 네 번째 생물 속성은 10000000001
이 문제는 시계를 칠 수 없고 메모리가 폭발할 수 있으며 귀속할 수 밖에 없다.
처음에 점차 문제가 생겼는데, 나중에 깨달았다
코드는 다음과 같습니다.
#include
#include
#include
#include
#include
#include
#include
#define ll long long
#define inf 0x3f3f3f3f
#define N 100010
using namespace std;
int n,k,q;
int v[20][N];
struct A{
    int a,b,c;
}x[N];
int dfs(int a,int c){
    if(a<=k)return v[a][c];
    if(x[a].a==1){
        return max(dfs(x[a].b,c),dfs(x[a].c,c));
    }else{
        return min(dfs(x[a].b,c),dfs(x[a].c,c));
    }
}
int main(){
    while(scanf("%d %d %d",&n,&k,&q)!=EOF){
        int a,b,c;
        for(int i=1;i<=k;i++){
            for(int j=1;j<=n;j++){
                scanf("%d",&a);
                v[i][j]=a;
            }
        }
        int t=k+1;
        while(q--){
            scanf("%d %d %d",&a,&b,&c);
            if(a==3){
                printf("%d
",dfs(b,c)); }else{ x[t].a=a;x[t].b=b;x[t++].c=c; } } } return 0; }

좋은 웹페이지 즐겨찾기