小蒟蒻皮皮鱼 @ 2020-07-03 18:01:10
MLE七个点
感觉不应该啊，求解答
#include<bits/stdc++.h>
using namespace std;
#define ls (t[cnt].l)
#define rs (t[cnt].r)
typedef long long ll;
const int N = 1100005;
int read()
{
int ans = 0;
char c = getchar(), last = ' ';
while(c < '0' || c > '9') last = c, c = getchar();
while(c >= '0' && c <= '9') ans = (ans << 1) + (ans << 3) + c - '0', c = getchar();
if(last == '-') ans = - ans;
return ans;
}
int cnt;
unsigned long long seed = 1;
int Rand()
{
seed *= 19260817;
return int(seed);
}
struct tree
{
int l, r, rad, siz;
int val;
}t[N];
void update(int cnt)
{
t[cnt].siz = t[ls].siz + t[rs].siz + 1;
}
int New(int x)
{
t[++cnt].val = x;
t[cnt].rad = Rand();
t[cnt].siz = 1;
return cnt;
}
void split(int cnt, int k, int &x, int &y)
{
if(!cnt)
{
x = y = 0;
return;
}
if(t[cnt].val <= k)
{
x = cnt;
split(rs, k, rs, y);
}
if(t[cnt].val > k)
{
y = cnt;
split(ls, k, x, ls);
}
update(cnt);
}
int merge(int x, int y)
{
if(x == 0) return y;
if(y == 0) return x;
if(t[x].rad <= t[y].rad)
{
t[x].r = merge(t[x].r, y);
update(x);
return x;
}
else
{
t[y].l = merge(x, t[y].l);
update(y);
return y;
}
}
int kth(int cnt, int k)
{
if(t[ls].siz + 1 == k) return t[cnt].val;
if(t[ls].siz >= k) return kth(ls, k);
else return kth(rs, k - t[ls].siz - 1);
}
int n, m, rt;
int last = 0, ans;
int main()
{
// freopen("1.in", "r", stdin);
// freopen("1.out", "w", stdout);
n = read(), m = read();
for(int i = 1; i <= n; i ++)
{
int k;
int x, y;
k = read();
split(rt, k, x, y);
rt = merge(merge(x, New(k)), y);
}
int k;
int opt, x, y, z;
for(int i = 1; i <= m; i ++)
{
opt = read(), k = read();
k ^= last;
if(opt == 1)
{
split(rt, k, x, y);
rt = merge(merge(x, New(k)), y);
}
if(opt == 2)
{
split(rt, k, x, y);
split(rt, k - 1, x, z);
z = merge(t[z].l, t[z].r);
rt = merge(merge(x, z), y);
}
if(opt == 3)
{
split(rt, k - 1, x, y);
last = t[x].siz + 1;
ans ^= last;
//printf("%lld\n", last);
rt = merge(x, y);
}
if(opt == 4)
{
last = kth(rt, k);
ans ^= last;
//printf("%lld\n", last);
}
if(opt == 5)
{
split(rt, k - 1, x, y);
last = kth(x, t[x].siz);
ans ^= last;
//printf("%lld\n", last);
rt = merge(x, y);
}
if(opt == 6)
{
split(rt, k, x, y);
last = kth(y, 1);
ans ^= last;
//printf("%lld\n", last);
rt = merge(x, y);
}
}
printf("%d", ans);
}by zhoukangyang @ 2020-07-03 18:05:39
@ZSH_ZSH 你看题了没
by zhoukangyang @ 2020-07-03 18:18:14
建议您的split里用else语句
by zhoukangyang @ 2020-07-03 18:18:43
我看不出来错，您看我的代码吧
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
int n,m,opt,us,spa,splx,sply,splz,root,las,cr;
struct node {
int son[2],siz,val,key;
} q[2000009];
void upd(int x) {q[x].siz=q[q[x].son[0]].siz+q[q[x].son[1]].siz+1;}
int new_root(int value) {++n,q[n].siz=1,q[n].val=value,q[n].key=rand();return n;}
int merge(int x,int y) { //x < y
if(!x||!y) return x+y;
if(q[x].key<q[y].key) {
q[x].son[1]=merge(q[x].son[1],y),upd(x);
return x;
}
else {
q[y].son[0]=merge(x,q[y].son[0]),upd(y);
return y;
}
}
void split(int now,int k,int &x,int &y) {
if(!now) x=y=0;
else {
if(q[now].val<=k) x=now,split(q[now].son[1],k,q[now].son[1],y);
else y=now,split(q[now].son[0],k,x,q[now].son[0]);
upd(now);
}
}
int kth(int now,int k) {
while(1) {
if(k<=q[q[now].son[0]].siz) now=q[now].son[0];
else if(k==q[q[now].son[0]].siz+1) return q[now].val;
else k-=q[q[now].son[0]].siz+1,now=q[now].son[1];
}
}
signed main() {
srand(1919810);
scanf("%d%d",&us,&m);
while(us--) scanf("%d",&cr),split(root,cr,splx,sply),root=merge(merge(splx,new_root(cr)),sply),cr=0;
while(m--) {
scanf("%d%d",&opt,&us),us^=las;
if(opt==1) split(root,us,splx,sply),root=merge(merge(splx,new_root(us)),sply);
if(opt==2) split(root,us,splx,sply),split(splx,us-1,splx,splz),splz=merge(q[splz].son[0],q[splz].son[1]),root=merge(merge(splx,splz),sply);
if(opt==3) split(root,us-1,splx,sply),las=q[splx].siz+1,root=merge(splx,sply),cr^=las;
if(opt==4) las=kth(root,us),cr^=las;
if(opt==5) split(root,us-1,splx,sply),las=kth(splx,q[splx].siz),root=merge(splx,sply),cr^=las;
if(opt==6) split(root,us,splx,sply),las=kth(sply,1),root=merge(splx,sply),cr^=las;
}
printf("%d\n",cr);
return 0;
} by water_lift @ 2020-07-03 18:19:47
我看不出来错，您看我的代码吧
#include <cstdio>
#include <cstdlib>
#define ll long long
#define re register
#define il inline
#define gc getchar
#define pc putchar
template <class T>
void read(T &x) {
re bool f = 0;
re char c = gc();
while ((c < '0' || c > '9') && c != '-') c = gc();
if (c == '-') f = 1, c = gc();
x = 0;
while (c >= '0' && c <= '9') x = x * 10 + (c ^ 48), c = gc();
f && (x = -x);
}
template <class T>
void print(T x) {
if (x < 0) pc('-'), x = -x;
if (x >= 10) print(x / 10);
pc((x % 10) ^ 48);
}
#define priln(x) do{print(x);pc('\n');}while(0)
#define prisp(x) do{print(x);pc(' ');}while(0)
const int N = 100005, S = N * 40;
int nc, ch[S][2], val[S], pri[S], siz[S];
il int newd(int x) {
val[++nc] = x;
ch[nc][0] = ch[nc][1] = 0;
pri[nc] = rand();
siz[nc] = 1;
return nc;
}
il void upd(int x) {
siz[x] = siz[ch[x][0]] + siz[ch[x][1]] + 1;
}
void split(int x, int k, int &a, int &b) {
if (!x) {a = b = 0; return;}
if (k < val[x]) {
split(ch[x][0], k, a, ch[x][0]);
b = x;
upd(b);
} else {
split(ch[x][1], k, ch[x][1], b);
a = x;
upd(a);
}
}
int merge(int a, int b) {
if (!a || !b) return a | b;
if (pri[a] < pri[b]) {
ch[a][1] = merge(ch[a][1], b);
upd(a);
return a;
} else {
ch[b][0] = merge(a, ch[b][0]);
upd(b);
return b;
}
}
int kth(int x, int k) {
if (k == siz[ch[x][0]] + 1) return val[x];
if (k < siz[ch[x][0]] + 1) return kth(ch[x][0], k);
else return kth(ch[x][1], k - siz[ch[x][0]] - 1);
}
int n, m, root;
int main() {
read(n);
read(m);
for (re int i = 1; i <= n; ++i)
{
re int x, a, b;
read(x);
split(root, x, a, b);
root = merge(a, merge(newd(x), b));
}
re int la = 0, ans = 0;
while (m--) {
re int opt, x;
read(opt);
read(x);
x ^= la;
if (opt == 1) {
re int a, b;
split(root, x, a, b);
root = merge(a, merge(newd(x), b));
} else if (opt == 2){
re int a, b, c;
split(root, x, b, c);
split(b, x - 1, a, b);
b = merge(ch[b][0], ch[b][1]);
root = merge(a, merge(b, c));
} else if (opt == 3) {
re int a, b;
split(root, x - 1, a, b);
la = siz[a] + 1;
ans ^= la;
root = merge(a, b);
} else if (opt == 4) {
la = kth(root, x);
ans ^= la;
} else if (opt == 5) {
re int a, b;
split(root, x - 1, a, b);
la = kth(a, siz[a]);
ans ^= la;
root = merge(a, b);
} else if (opt == 6) {
re int a, b;
split(root, x, a, b);
la = kth(b, 1);
ans ^= la;
root = merge(a, b);
}
}
priln(ans);
}by pikabi @ 2020-07-03 18:27:28
您的cnt是不是重名了？
by SamariumPhosphide @ 2020-07-03 19:03:21
查不出来，看我的代码
#include <bits/stdc++.h>
#define SZ(x) (x?x->sz:0)
using namespace std;
const int N=1100010;
struct Node{
int sz,rk,dat;
Node *lson,*rson;
void update() {
sz=SZ(lson)+SZ(rson)+1;
}
};
int n,m,cnt,lastans,ans;
Node pool[N<<1];
Node *rt;
inline int read() {
int x = 0, f = 1; char c = getchar();
while (!isdigit(c)) {
if (c == '-') f = -1;
c = getchar();
}
while (isdigit(c)) {
x = x * 10 + c - '0';
c = getchar();
}
return x * f;
}
void split(Node *p,Node *&pl, Node *&pr, int x){
if(!p){pl=pr=NULL;return;}
if(p->dat<=x){
pl=p;split(p->rson,pl->rson,pr,x);
pl->update();
}else{
pr=p;split(p->lson,pl,pr->lson,x);
pr->update();
}
}
void merge(Node*& p,Node* pl,Node* pr){
if(!pl||!pr){p=pl?pl:pr;return;}
if(pl->rk<pr->rk){
p=pl;merge(p->rson,pl->rson,pr);
}else{
p=pr;merge(p->lson,pl,pr->lson);
}
p->update();
}
Node *newNode(int x){
Node* newN=pool+(++cnt);
newN->dat=x;
newN->rk=rand();
newN->sz=1;
return newN;
}void insert(Node*& rt,int x){
Node *l,*r;
split(rt,l,r,x-1);
merge(rt,l,newNode(x));
merge(rt,rt,r);
}void del(Node*& rt,int x){
Node *p1,*p2,*p3,*p4;
split(rt,p1,p2,x-1);
split(p2,p3,p4,x);
merge(p3,p3->lson,p3->rson);
merge(p3,p3,p4);
merge(rt,p1,p3);
}int getRk(Node*& rt,int x){
Node *l,*r;
split(rt,l,r,x-1);
int ans=SZ(l)+1;
merge(rt,l,r);
return ans;
}int kth(Node *cur,int k){
while(cur){
if(SZ(cur->lson)>=k){
cur=cur->lson;
}else if(k>SZ(cur->lson)+1){
k-=SZ(cur->lson)+1;cur=cur->rson;
}else{
return cur->dat;
}
}
return 0;
}int pre(Node *cur,int x){
int ans=INT_MIN;
while(cur){
if(x>cur->dat){
ans=max(ans,cur->dat);
cur=cur->rson;
}else{
cur=cur->lson;
}
}
return ans;
}int succ(Node *cur,int x){
int ans=INT_MAX;
while (cur){
if(x<cur->dat){
ans=min(ans,cur->dat);
cur=cur->lson;
}else{
cur=cur->rson;
}
}
return ans;
}
signed main() {
srand(time(0));
n=read(),m=read();
for(int i=1;i<=n;i++){
int x=read();insert(rt,x);
}
while(m--){
int opt=read(),x=read();
x^=lastans;
// printf("LOGOUT: %d %d\n", opt, x);
if(opt==1){
insert(rt,x);
}else if(opt==2){
del(rt,x);
}else if(opt==3){
lastans=getRk(rt,x);ans^=lastans;
}else if(opt==4){
lastans=kth(rt,x);ans^=lastans;
}else if(opt==5){
lastans=pre(rt,x);ans^=lastans;
}else{
lastans=succ(rt,x);ans^=lastans;
}
}
printf("%d\n",ans);
return 0;
}by syksykCCC @ 2020-07-03 19:15:38
看不出来错，顺手膜拜
by Rubidium_Chloride @ 2020-07-03 19:16:30
不是怎么都发代码了呀呀呀
by 小蒟蒻皮皮鱼 @ 2020-07-03 19:25:30
一个zz地方写错了，此贴终结
by 小蒟蒻皮皮鱼 @ 2020-07-03 19:25:55
split(rt, k - 1, x, z);