c++ list 使用
- #include <cstdio>
- #include <cstdlib>
- #include <cmath>
- #include <cstring>
- #include <time.h>
- #include <string>
- #include <set>
- #include <map>
- #include <list>
- #include <ext/rope>
- #include <stack>
- #include <queue>
- #include <vector>
- #include <bitset>
- #include <algorithm>
- #include <iostream>
- using namespace std;
- #define ll long long
- #define minv 1e-6
- #define inf 1e9
- #define pi 3.1415926536
- #define E 2.7182818284
- const ll mod=1e9+7;//998244353
- const int maxn=150010;
- using namespace __gnu_cxx;
- char ch;
- void read(int &x){
- ch = getchar();x = 0;
- for (; ch <'0' || ch> '9'; ch = getchar());
- for (; ch>='0' && ch <= '9'; ch = getchar()) x = x * 10 + ch - '0';
- }
- list<int>f[maxn];
- int main()
- {
- int n,q,mode,u,w,val,v,i;
- while (~scanf("%d%d",&n,&q))
- {
- for (i=1;i<=n;i++)
- f[i].clear();
- while (q--)
- {
- read(mode);
- if (mode==1)
- {
- read(u),read(w),read(val);
- if (w)
- f[u].push_back(val);
- else
- f[u].push_front(val);
- }
- //2
- else if (mode==2)
- {
- read(u),read(w);
- if (f[u].empty())
- printf("-1\n");
- else
- {
- if (w)
- {
- printf("%d\n",f[u].back());
- f[u].pop_back();
- }
- else
- {
- printf("%d\n",f[u].front());
- f[u].pop_front();
- }
- }
- }
- //3
- else
- {
- read(u),read(v),read(w);
- if (w)
- reverse(f[v].begin(),f[v].end());
- f[u].splice(f[u].end(),f[v]);
- //or
- // if (w)
- // f[u].insert(f[u].end(),f[v].rbegin(),f[v].rend());
- // else
- // f[u].insert(f[u].end(),f[v].begin(),f[v].end());
- f[v].clear();
- }
- }
- }
- return 0;
- }
- /*
- 2 30
- 1 1 0 123
- 1 1 0 1234
- 1 2 1 2333
- 1 2 1 23333
- 1 2 1 233333
- 1 2 1 2333333
- 1 2 1 23333333
- 2 2 0
- 2 2 1
- 3 1 2 1
- 2 1 1
- 2 1 1
- 2 1 1
- 2 1 1
- 2 1 1
- 2 1 1
- 3 1 5 0
- 1 5 1 1
- 2 5 1
- */
用 rope 超时了
- #include <cstdio>
- #include <cstdlib>
- #include <cmath>
- #include <cstring>
- #include <time.h>
- #include <string>
- #include <set>
- #include <map>
- #include <list>
- #include <ext/rope>
- #include <stack>
- #include <queue>
- #include <vector>
- #include <bitset>
- #include <algorithm>
- #include <iostream>
- using namespace std;
- #define ll long long
- #define minv 1e-6
- #define inf 1e9
- #define pi 3.1415926536
- #define E 2.7182818284
- const ll mod=1e9+7;//998244353
- const int maxn=150010;
- using namespace __gnu_cxx;
- void read(int &x){
- char ch = getchar();x = 0;
- for (; ch <'0' || ch> '9'; ch = getchar());
- for (; ch>='0' && ch <= '9'; ch = getchar()) x = x * 10 + ch - '0';
- }
- rope<int>f[maxn],ff[maxn];
- int main()
- {
- int n,q,mode,u,w,val,v,i;
- while (~scanf("%d%d",&n,&q))
- {
- for (i=1;i<=n;i++)
- f[i].clear(),ff[i].clear();
- while (q--)
- {
- read(mode);
- if (mode==1)
- {
- read(u),read(w),read(val);
- if (w==1)
- {
- f[u].push_back(val);
- ff[u].insert(0,val);
- }
- else
- {
- f[u].insert(0,val);
- ff[u].push_back(val);
- }
- }
- else if (mode==2)
- {
- read(u),read(w);
- if (f[u].empty())
- printf("-1\n");
- else
- {
- if (w==1)
- {
- printf("%d\n",f[u].at(f[u].size()-1));
- f[u].erase(f[u].size()-1,1);
- ff[u].erase(0,1);
- }
- else
- {
- printf("%d\n",f[u].at(0));
- f[u].erase(0,1);
- ff[u].erase(f[u].size()-1,1);
- }
- }
- }
- else
- {
- read(u),read(v),read(w);
- if (w==0)
- {
- f[u].append(f[v]);
- ff[u]=ff[v]+ff[u];
- f[v].clear();
- ff[v].clear();
- }
- else
- {
- f[u].append(ff[v]);
- ff[u]=f[v]+ff[u];
- f[v].clear();
- ff[v].clear();
- }
- }
- }
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2737223.html