沙盒测试-前缀和

输入样例:

5 3 RURDL 1 2 3 5 1 5

输出样例:

2 0

错误代码（超时） 最坏4*10的10次方

importjava.io.BufferedReader;importjava.io.IOException;importjava.io.InputStreamReader;publicclassMain{publicstaticvoidmain(String[]args)throwsIOException{BufferedReaderbf=newBufferedReader(newInputStreamReader(System.in));String[]s=bf.readLine().split(" ");intn=Integer.parseInt(s[0]);intq=Integer.parseInt(s[1]);intx=0;inty=0;char[]chars=bf.readLine().toCharArray();for(inti=0;i<q;i++){String[]s1=bf.readLine().split(" ");inta=Integer.parseInt(s1[0])-1;intb=Integer.parseInt(s1[1]);for(intj=a;j<b;j++){if(chars[j]=='L'){x--;}elseif(chars[j]=='R'){x++;}elseif(chars[j]=='U'){y++;}elseif(chars[j]=='D'){y--;}}}System.out.println(x+" "+y);}}

正确代码(前缀和)

importjava.io.BufferedReader;importjava.io.IOException;importjava.io.InputStreamReader;publicclassMain{publicstaticvoidmain(String[]args)throwsIOException{BufferedReaderbf=newBufferedReader(newInputStreamReader(System.in));String[]first=bf.readLine().split(" ");intn=Integer.parseInt(first[0]);intq=Integer.parseInt(first[1]);char[]chars=bf.readLine().toCharArray();// 前缀位移数组int[]px=newint[n+1];int[]py=newint[n+1];for(inti=1;i<=n;i++){px[i]=px[i-1];py[i]=py[i-1];charc=chars[i-1];if(c=='L'){px[i]--;}elseif(c=='R'){px[i]++;}elseif(c=='U'){py[i]++;}elseif(c=='D'){py[i]--;}}intx=0,y=0;for(inti=0;i<q;i++){String[]query=bf.readLine().split(" ");intl=Integer.parseInt(query[0]);intr=Integer.parseInt(query[1]);x+=px[r]-px[l-1];y+=py[r]-py[l-1];}System.out.println(x+" "+y);}}