代码量不到十行的pbds 10pts求调

断清秋 @ 2021-10-17 23:38:29

#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#define ll long long
#define back return
#define ri register int
#define ull unsigned ll
#define node pair<ll,ll>
using namespace std;
using namespace __gnu_pbds;
tree<node,null_type,less<node>,rb_tree_tag,tree_order_statistics_node_update> t;
ll read()
{
    ll x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-')
            f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    {
        x=x*10+ch-'0';
        ch=getchar();
    }
    back x*f;
}
ll n,m,last,opt,x,res;
unordered_map<ll,ll> cnt;
int main()
{
    n=read(),m=read();
    for(ri i=1;i<=n;i++)
        x=read(),t.insert(node(x,++cnt[x]));    
    for(ri i=1;i<=m;i++)
    {       
        opt=read(),x=read();
        x^=last;
        if(opt==1)
            t.insert(node(x,++cnt[x]));
        if(opt==2)
            t.erase(t.lower_bound(node(x,cnt[x]--)));
        if(opt==3)
            last=t.order_of_key(node(x,1))+1,res^=last;
        if(opt==4)
            last=t.find_by_order(x-1)->first,res^=last;
        if(opt==5)
            last=(--t.lower_bound(node(x,1)))->first,res^=last;
        if(opt==6)
            last=t.upper_bound(node(x+1,1))->first,res^=last;
    }
    cout<<res<<"\n";
    back 0;
}

by ud2_ @ 2021-10-17 23:43:37

《不到十行》

by 断清秋 @ 2021-10-17 23:45:56

@ud2_ 确实啊，核心代码六行

by 断清秋 @ 2021-10-18 00:04:02

@ud2_ 您是不是A了……能问一下是哪个位置错了吗/yiw

by ud2_ @ 2021-10-18 00:04:57

anyway，这样能过：

@@ -1,7 +1,7 @@
 #include<bits/stdc++.h>
 #include<ext/pb_ds/assoc_container.hpp>
 #include<ext/pb_ds/tree_policy.hpp>
-#define ll long long
+#define ll int
 #define back return
 #define ri register int
 #define ull unsigned ll
@@ -27,20 +27,20 @@
     back x*f;
 }
 ll n,m,last,opt,x,res;
-unordered_map<ll,ll> cnt;
+ll cnt;
 int main()
 {
     n=read(),m=read();
     for(ri i=1;i<=n;i++)
-        x=read(),t.insert(node(x,++cnt[x]));
+        x=read(),t.insert(node(x,++cnt));
     for(ri i=1;i<=m;i++)
     {
         opt=read(),x=read();
         x^=last;
         if(opt==1)
-            t.insert(node(x,++cnt[x]));
+            t.insert(node(x,++cnt));
         if(opt==2)
-            t.erase(t.lower_bound(node(x,cnt[x]--)));
+            t.erase(t.lower_bound(node(x,1)));
         if(opt==3)
             last=t.order_of_key(node(x,1))+1,res^=last;
         if(opt==4)
@@ -48,7 +48,7 @@
         if(opt==5)
             last=(--t.lower_bound(node(x,1)))->first,res^=last;
         if(opt==6)
-            last=t.upper_bound(node(x+1,1))->first,res^=last;
+            last=t.upper_bound(node(x,0x7fffffff))->first,res^=last;
     }
     cout<<res<<"\n";
     back 0;

by 断清秋 @ 2021-10-18 09:15:03

@ud2_ dbq我太菜了，但是我还是不明白这样为什么是对的/dk

by ud2_ @ 2021-10-18 18:55:57

@断清秋 az

操作 2 删掉(数值为 x 的元素中编号最小的)比较方便。操作 6 要找大于(数值为 x 的元素中编号最大的)。然后改成 int 类型，所有值共用一个计数器，节省点空间。

by 断清秋 @ 2021-10-18 18:57:40

@ud2_ 但是共用一个计数器怎么能实现单个元素去重呢QAQ

by ud2_ @ 2021-10-18 19:05:20

去重……？为什么去重？

by 断清秋 @ 2021-10-18 19:13:11

@ud2_ 啊这 erase操作不是会删除所有值为 x 的元素吗 所以需要去重啊