dys

qq:1115410174 西北大学

1.7万

dys
3天前
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
using namespace std;
int n,m;
const int N = 1e5+10;
struct node{
int s[2],p,v;
int sum,rev;
}tr[N];
int stk[N];
void pushup(int x){
tr[x].sum = tr[tr[x].s[0]].sum ^ tr[x].v ^ tr[tr[x].s[1]].sum;
}
void pushrev(int x){
swap(tr[x].s[0],tr[x].s[1]);
tr[x].rev ^= 1;
}
void pushdown(int x){
if(tr[x].rev){
pushrev(tr[x].s[0]);
pushrev(tr[x].s[1]);
tr[x].rev ^= 1;
}
}
bool isroot(int x){
return tr[tr[x].p].s[0]!=x&&tr[tr[x].p].s[1]!=x;
}
void rotate(int x){
int y = tr[x].p,z = tr[y].p;
int k = tr[y].s[1] == x;
if(!isroot(y)) tr[z].s[tr[z].s[1] == y] = x;
tr[x].p = z;
tr[y].s[k] = tr[x].s[k^1];
tr[tr[x].s[k^1]].p = y;
tr[x].s[k ^ 1] = y;
tr[y].p = x;
pushup(y);
pushup(x);
}
void splay(int x){
int top = 0,r = x;
stk[++top] = r;
while(!isroot(r)) stk[++top] = r = tr[r].p;
while(top) pushdown(stk[top--]);
while(!isroot(x)){
int y = tr[x].p,z = tr[y].p;
if(!isroot(y))
if((tr[y].s[1] == x)^(tr[z].s[1] == y)) rotate(x);
else rotate(y);
rotate(x);
}
}
void access(int x){
int z = x;
for(int y = 0;x;y = x,x = tr[x].p){
splay(x);
tr[x].s[1] = y;
pushup(x);
}
splay(z);
}
void makeroot(int x){
access(x);
pushrev(x);
}
int findroot(int x){
access(x);
while(tr[x].s[0]) pushdown(x),x = tr[x].s[0];
splay(x);
return x;
}
void split(int x,int y){
makeroot(x);
access(y);
}
makeroot(x);
if(findroot(y) != x) tr[x].p = y;
}
void cut(int x,int y){
makeroot(x);
if(findroot(y) == x && tr[y].p == x && !tr[y].s[0]){
tr[x].s[1] = tr[y].p = 0;
pushup(x);
}
}
int main(){
cin >> n >> m;
for(int i=1;i<=n;i++) cin >> tr[i].v;
int op,x,y,w;
while(m--){
cin >> op;
if(op == 0){
cin >> x >> y;
split(x,y);
cout<< tr[y].sum <<endl;
}else if(op == 1){
cin >> x >> y;
}else if(op == 2){
cin >> x >> y;
cut(x,y);
}else{
cin >> x >> w;
splay(x);
tr[x].v = w;
pushup(x);
}
}
return 0;
}


dys
6天前
#include<bits/stdc++.h>
using namespace std;
const int N = 4e7+10;
char a[N],b[N];
int p[N];
int len;
void init(){
int k = 0;
b[k++] = '\$';
b[k++] = '#';
for(int i=0;i<len;i++){
b[k++] = a[i];
b[k++] = '#';
}
b[k++] = '^';
len = k;
}
void manacher(){
int mr = 1,mid;
for(int i=0;i<len;i++){
if(i < mr) p[i] = min(p[2*mid-i],mr-i);
else p[i] = 1;
while(b[i-p[i]] == b[i+p[i]]) p[i]++;
if(i + p[i] > mr){
mr = i + p[i];
mid = i;
}
}
}
int main(){
scanf("%s",a);
len = strlen(a);
init();
manacher();
int ans = 0;
for(int i=0;i<len;i++) ans = max(ans,p[i]);
cout<<ans - 1<<endl;
return 0;
}


dys
9天前
#include<bits/stdc++.h>
using namespace std;
const int N = 105;
int a[N][N];
int main(){
int n,m;
cin>>n>>m;
int x = 1,y = 1;
int dx[]={-1,0,1,0},dy[]={0,1,0,-1};
int s = 0;
for(int i=1;i<=n*m;i++){
a[x][y] = i;
int sx = x + dx[s];
int sy = y + dy[s];
if(sx<1 || sy<1 || sx>n || sy>m || a[sx][sy]){
s = (s+1)%4;
sx = x + dx[s];
sy = y + dy[s];
}
x = sx;
y = sy;
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++)
cout<<a[i][j]<<" ";
cout<<endl;
}
return 0;
};


dys
12天前
#include<bits/stdc++.h>
using namespace std;
const int N = 2e5+10;
int l[N],r[N],d[N],v[N],p[N],idx;
int n;
int find(int x){
if(p[x]!=x) p[x] = find(p[x]);
return p[x];
}
int cmp(int x,int y){
if(v[x]!=v[y]) return v[x]<v[y];
return x<y;
}
int merge(int x,int y){
if(!x || !y) return x+y;
if(cmp(y,x)) swap(x,y);
r[x] = merge(r[x],y);
if(d[r[x]] > d[l[x]]) swap(l[x],r[x]);
d[x] = d[r[x]] + 1;
return x;
}
int main(){
scanf("%d",&n);
int op,a,x,y;
v[0] = 2e9;
while(n--){
cin>>op;
if(op == 1){
cin>>x;
v[++idx] = x;
d[idx] = 1;
p[idx] = idx;
}else if(op == 2){
cin>>x>>y;
x = find(x),y = find(y);
if(x == y) continue;
if(cmp(y,x)) swap(x,y);
p[y] = x;
merge(x,y);
}else if(op == 3){
cin>>x;
cout<<v[find(x)]<<endl;
}else{
cin>>x;
x = find(x);
if(cmp(r[x],l[x])) swap(r[x],l[x]);
p[x] = l[x],p[l[x]] = l[x];
merge(l[x],r[x]);
}
}
return 0;
}


dys
13天前
#pragma GCC optimize(2)
#include<bits/stdc++.h>
using namespace std;
const int N=100000+10;
int a[N];
int main(){
int res,ans=0;
int n;
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
sort(a+1,a+n+1);
if(n%2==1) res=a[n/2+1];
else res=a[n/2];
for(int i=1;i<=n;i++) ans+=abs(a[i]-res);
cout<<ans<<endl;
return 0;
}


dys
13天前
#include<bits/stdc++.h>
using namespace std;
int n;
const int N = 1e5+10;
typedef long long ll;
ll a[N];
int main(){
cin>>n;
for(int i=0;i<n;i++) cin>>a[i];
int k = 0;
for(int i=62;i>=0;i--){
for(int j=k;j<n;j++)
if(a[j] >> i & 1)
{
swap(a[k],a[j]);
break;
}
if(!(a[k]>>i&1)) continue;
for(int j=0;j<n;j++)
if(j!=k && a[j] >> i & 1)
a[j]^=a[k];
k++;
if(k == n) break;
}
ll ans = 0;
for(int i=0;i<k;i++) ans^=a[i];
cout<<ans<<endl;
return 0;
}


dys
14天前

dys
14天前
#include<bits/stdc++.h>
using namespace std;
int n,m;
typedef long long ll;
int gcd(int a,int b){
return b?gcd(b,a%b):a;
}
ll C(int a){
return (ll)a*(a-1)*(a-2)/6;
}
int main(){
cin>>n>>m;
n++,m++;
ll res = C(n*m)-m*C(n)-n*C(m);
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
res-=2ll*(gcd(i,j)-1)*(n-i)*(m-j);//i,j为长度
}
}
cout<<res<<endl;
return 0;
}


dys
14天前
class Solution {
public:
int deleteAndEarn(vector<int>& nums) {
if(nums.size() == 1) return nums[0];
unordered_map<int,int> cnt;
int n = nums.size();
for(int i=0;i<n;i++){
cnt[nums[i]]++;
}
vector<int>f(10001,0);
int res = 0;
f[0] = 0;
for(int i=1;i<10001;i++){
f[i] = cnt[i]*i;
if(i>=2 && cnt.count(i)) f[i] = max(f[i-1],f[i-2]+cnt[i]*i);
res = max(res,f[i]);
}
return res;
}
};


dys
15天前

#include<bits/stdc++.h>
using namespace std;
const int N = 4e4+10,INF = 1e9;
typedef long long ll;
struct node{
int s[2],p,v;
int size;
void init(int _p,int _v){
p = _p;
v = _v;
size = 1;
}
}tr[N];
int root,idx;
void pushup(int x){
tr[x].size = tr[tr[x].s[0]].size + tr[tr[x].s[1]].size + 1;
}
void rotate(int x){
int y = tr[x].p ,z = tr[y].p;
int k = tr[y].s[1] == x;
tr[z].s[tr[z].s[1] == y] = x;
tr[x].p = z;
tr[y].s[k] = tr[x].s[k^1];
tr[tr[x].s[k^1]].p = y;
tr[x].s[k^1] = y;
tr[y].p = x;
pushup(y);
pushup(x);
}
void splay(int x,int k){
while(tr[x].p != k){
int y = tr[x].p,z = tr[y].p;
if(z!=k)
if((tr[y].s[1] == x)^(tr[z].s[1] == y)) rotate(x);
else rotate(y);
rotate(x);
}
if(!k) root = x;
}
void insert(int v){
int u = root,p = 0;
while(u) p = u,u = tr[u].s[v > tr[u].v];
u = ++idx;
if(p) tr[p].s[v > tr[p].v] = u;
tr[u].init(p,v);
splay(u,0);
}
int get_prev(int v){
int u = root,res = 0;
while(u){
if(tr[u].v <= v) res = u,u = tr[u].s[1];
else u = tr[u].s[0];
}
//splay(u,0);
// if(res){
//     splay(res,0);
//     return tr[res].v;
// }
return res;
}
int get_next(int v){
int u = root,res = 0;
while(u){
if(tr[u].v >= v) res = u,u = tr[u].s[0];
else u = tr[u].s[1];
}
// if(res){
//     splay(u,0);
//     return tr[res].v;
// }
return res;
}
int main(){
int n;
cin>>n;
int x;
cin>>x;
insert(-INF);
insert(INF);
insert(x);
ll res = x;
--n;
while(n--){
cin>>x;
int a = tr[get_prev(x)].v;
int b = tr[get_next(x)].v;
res+=min(abs(a-x),abs(b-x));
splay(get_prev(x),0);
splay(get_prev(x),0);
insert(x);
}
cout<<res<<endl;
return 0;
}