C~G Java题解
最佳的方式就是分段的连续的段，直到删完，因为要是两段存在包含，那么删除外边的一大段次数减1，更优，因此记录每个下标结尾的删完需要的最少次数，另外还要记录一下之前同数字之前所有删完的最少次数以备查阅，时间复杂度O(n)
import java.util.*;
public class Main{
public static void main(String args[]){
Scanner sc=new Scanner(System.in);
int n=sc.nextInt(),a[]=new int[n],last[]=new int[500005],ans[]=new int[n+1];
Arrays.fill(last,n+10);
for(int i=0;i<n;i++){
a[i]=sc.nextInt();
ans[i+1]=1+last[a[i]];
last[a[i]]=Math.min(last[a[i]],ans[i]);
}
System.out.println(ans[n]<=n?ans[n]:-1);
}
}
简单版的可以逐行差分，，复杂版本参考链接，叫什么切比雪夫转化的坐标变换，也不知道为啥，，，哎，时间复杂度O(p^2)，其中p==3000
import java.util.*;
public class Main{
public static void main(String args[]){
Scanner sc=new Scanner(System.in);
int n=sc.nextInt(),m=sc.nextInt(),count[][]=new int[6100][6100],ans=0;
for(int i=0;i<m;i++){
int x=sc.nextInt(),y=sc.nextInt(),r=sc.nextInt(),px=x+y,py=x-y+3002;
count[Math.max(px-r,1)][Math.max(py-r,1)]^=1;
count[Math.max(px-r,1)][Math.min(py+r+1,6010)]^=1;
count[Math.min(px+r+1,6010)][Math.max(py-r,1)]^=1;
count[Math.min(px+r+1,6010)][Math.min(py+r+1,6010)]^=1;
}
for(int i=1;i<=6002;i++){
for(int j=1;j<=6002;j++){
count[i][j]^=count[i-1][j-1]^count[i][j-1]^count[i-1][j];
if(check(n,i,j)){
ans+=count[i][j];
}
}
}
System.out.println(ans);
}
static boolean check(int n,int a,int b){
if((a-b)%2==0){
int x=(a+b-3002)/2,y=(a-b+3002)/2;
return x>=1&&x<=n&&y>=1&&y<=n;
}
return false;
}
}
线段树记录正向哈希以及反向哈希，修改和求哈希是需要修改懒标记的，时间复杂度O(n+q*(logn)^2)
import java.io.*;
public class Main{
static long base=137,mod=(int)1e9+7,pre[]=new long[200005];
public static void main(String args[]) throws IOException{
BufferedReader bf=new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));
String arr[]=bf.readLine().split(" ");
int n=Integer.parseInt(arr[0]),q=Integer.parseInt(arr[1]);
pre[0]=1;
for(int i=1;i<=n;i++){
pre[i]=(pre[i-1]*base+1)%mod;
}
String s=bf.readLine();
SegTree st=new SegTree(0,n-1);
build(st,s);
for(int i=0;i<q;i++){
arr=bf.readLine().split(" ");
if(arr[0].equals("1")){
int l=Integer.parseInt(arr[1])-1,r=Integer.parseInt(arr[2])-1;
bw.write(check(st,l,r)?"YES\n":"NO\n");
}
else{
int l=Integer.parseInt(arr[1])-1,r=Integer.parseInt(arr[2])-1;
char c=arr[3].charAt(0);
modify(st,l,r,c);
}
}
bw.flush();
}
static boolean check(SegTree st,int a,int b){
if(find(st,a,b,1)==find(st,a,b,2)){
return true;
}
int s1=a+(b-a-1)/2,s2=b-(b-a-1)/2,l=-1,r=(b-a-1)/2;
while(l<r){
int mid=l+(r-l)/2;
if(find(st,s1-mid,s1,1)==find(st,s2,s2+mid,2)){
l=mid;
}
else{
r=mid-1;
}
if(l==r-1){
if(find(st,s1-r,s1,1)==find(st,s2,s2+r,2)){
l=r;
}
break;
}
}
return find(st,a,s1-l-2,1)==find(st,s2+l+2,b,2);
}
static void modify(SegTree st,int a,int b,int c){
int l=st.l,r=st.r;;
if(a==l&&b==r){
st.cur=c;
st.hash1=st.hash2=pre[r-l]*c%mod;
}
else{
clear(st);
int mid=(l+r)>>1;
if(b<=mid){
modify(st.left,a,b,c);
}
else if(a>mid){
modify(st.right,a,b,c);
}
else{
modify(st.left,a,mid,c);
modify(st.right,mid+1,b,c);
}
update(st);
}
}
static long find(SegTree st,int a,int b,int c){
if(a>b){
return 0;
}
int l=st.l,r=st.r;
if(l==a&&r==b){
return c==1?st.hash1:st.hash2;
}
clear(st);
int mid=(l+r)>>1;
if(b<=mid){
return find(st.left,a,b,c);
}
else if(a>mid){
return find(st.right,a,b,c);
}
long part1=find(st.left,a,mid,c),part2=find(st.right,mid+1,b,c);
return c==1?(part1+part2*pow(mid+1-a))%mod:(part2+part1*pow(b-mid))%mod;
}
static void build(SegTree st,String s){
int l=st.l,r=st.r;
if(l==r){
st.hash1=st.hash2=s.charAt(l);
}
else{
int mid=(l+r)>>1;
st.left=new SegTree(l,mid);
st.right=new SegTree(mid+1,r);
build(st.left,s);
build(st.right,s);
update(st);
}
}
static void update(SegTree st){
//子节点更新父节点
int l=st.l,r=st.r,mid=(l+r)>>1;
st.hash1=(st.left.hash1+st.right.hash1*pow(mid+1-l))%mod;
st.hash2=(st.right.hash2+st.left.hash2*pow(r-mid))%mod;
}
static void clear(SegTree st){
//父节点更新子节点
int l=st.l,r=st.r;
if(st.cur==-1||l==r){
return;
}
int mid=(l+r)>>1;
st.left.hash1=st.left.hash2=(st.cur*pre[mid-l])%mod;
st.right.hash2=st.right.hash1=(st.cur*pre[r-mid-1])%mod;
st.left.cur=st.cur;
st.right.cur=st.cur;
st.cur=-1;
}
static long pow(int a){
return (pre[a]+mod-pre[a-1])%mod;
}
}
class SegTree{
SegTree left,right;
int l,r,cur;
//hash1表示的左边低次哈希，hash2右边低次
long hash1,hash2;
public SegTree(int l,int r){
this.l=l;
this.r=r;
cur=-1;
}
}
京公网安备 11010502036488号