uva 12657 解法超时了，求方法提高速度

Question

#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include<string>
#include<iostream>
#include<list>
using namespace std;
int main() {
    int n = 0, m = 0;
    while (scanf("%d%d",&n,&m) == 2) {
        list<long long int>one;
        for (long long int i = 1; i <= n; i++) {
            one.push_back(i);
        }
        for (long long int j = 1; j <= m; j++) {
            long long int t = 0, k = 0, q = 0;
            long long int x = 0, y = 0;
            list<long long int>::iterator fr, sc;
            scanf("%d", &t);
            switch (t){
            case 1:
            case 2:
            case 3:
                scanf("%d%d", &k, &q); if (k == q)continue;
                for (fr = one.begin(); *fr != k; fr++, x++);
                for (sc = one.begin(); *sc != q; sc++, y++);
            switch (t) {
            case 1:
                if (x==y-1) continue;
                else { one.insert(sc, *fr); one.erase(fr); }
                break;
            case 2:
                if (x==y+1) continue;/*insert的本质*/
                else { one.insert(++sc, *fr); one.erase(fr); }
                break;
            case 3:
                swap(*fr, *sc);
                break;
            }
                break;
            case 4:
                one.reverse();
                break;
            default:
                continue;
            }
        }
        long long int  sum = 0, k = 1;
        list<long long int>::iterator it;
        for (it=one.begin(); it!=one.end(); it++, k++)if (k % 2 != 0)sum += *it;
        ::cout << sum;
        ::cout << "\n";
    }
    return 0;
}

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<list>
using namespace std;
int main() {
    int n = 0, m = 0;
    while (scanf("%d%d",&n,&m) == 2) {
        long long int num[100005] = { 0 };
        for (long long int i = 1; i <= n; i++) {
            num[i - 1] = i;
        }
        list<long long int>one(num,num+n);
        for (long long int j = 1; j <= m; j++) {
            int t = 0, k = 0, q = 0;
            int x = 0, y = 0;
            list<long long int>::iterator fr, sc;
            scanf("%d", &t);
            switch (t){
            case 1:
            case 2:
            case 3:
                scanf("%d%d", &k, &q); if (k == q)continue;
                for (fr = one.begin(); *fr != k; fr++, x++);
                for (sc = one.begin(); *sc != q; sc++, y++);
            switch (t) {
            case 1:
                if (x==y-1) continue;
                else { one.insert(sc, *fr); one.erase(fr); }
                break;
            case 2:
                if (x==y+1) continue;/*insert的本质*/
                else { one.insert(++sc, *fr); one.erase(fr); }
                break;
            case 3:
                swap(*fr, *sc);
                break;
            }
                break;
            case 4:
                one.reverse();
                break;
            default:
                continue;
            }
        }
        long long int  sum = 0, k = 1;
        list<long long int>::iterator it;
        for (it=one.begin(); it!=one.end(); it++, k++)if (k % 2 != 0)sum += *it;
        ::cout << sum;
        ::cout << "\n";
    }
    return 0;
}

Answer 1

#include<bits/stdc++.h>
using namespace std;
int r[100005],l[100005];
void link(int a,int b)
{
    r[a]=b;l[b]=a;
}
int main()
{
    int n,m,op,x,y,flag=0,cas=0;
    while(scanf("%d %d",&n,&m)==2)
    {
        for(int i=1;i<=n;i++)
        {
            r[i]=(i+1)%(n+1);
            l[i]=i-1;
        }
        r[0]=1;
        l[0]=n;
        flag=0;
        while(m--)
        {
            scanf("%d",&op);
            if(op!=4)
            scanf("%d %d ",&x,&y);
            else
            flag=!flag;
            if(op==3&&r[x]==y)
            swap(x,y);
            if(op<3&&flag)
            op=3-op;
            if(op==1&&l[y]==x)
            continue;
            if(op==2&&r[y]==x)
            continue;
            int rx=r[x],lx=l[x],ry=r[y],ly=l[y];
            if(op==1)
            {
                link(lx,rx);
                link(ly,x);
                link(x,y);
            }
            if(op==2)
            {
                link(lx,rx);
                link(y,x);
                link(x,ry);
            }
            if(op==3)
            {
                if(l[x]==y)
                {
                    link(ly,x);
                    link(x,y);
                    link(y,rx);
                }
                else
                {
                    link(lx,y);
                    link(y,rx);
                    link(ly,x);
                    link(x,ry);
                }
            }
        }
        int k=0;
        long long ans=0;
        for(int i=1;i<=n;i++)
        {
            k=r[k];
            if(i%2==1)
            ans+=k;
        }
        //cout<<(long long)n/2*(n+1)<<endl;
        if(flag&&n%2==0)
            ans=(long long)n/2*(n+1)-ans;
        printf("Case %d: %lld\n",++cas,ans);
    }
    return 0;
 }